C++

Forum

 
Task

Krenkov (2)
Help for task. Two players are playing the game "Risk".


This game is played on the pattern of cities that are interconnected by roads. If two cities are directly related to the path, those cities are considered adjacent. Each player can set up base in the city and then the city is considered to be conquered by that player. For setting the base in a city the player spends a coin. However, the player can set up base in a city, if already set his base in a neighboring town.
In a city can not have more than one base, or the city could be won only by a single player.
Kosta currently has won B1 cities and Kiril has won B2 cities and we know who they are. Kosta now wants to use all the remaining coins (which can) to increase the number of conquered cities.
As we explained, the number of conquered towns can increase so that from some of the conquered city, you can go to a neighboring town which is free and for one coin set base. This can be done as long as there are coins. .

If the pattern of cities is given, as well as cities that have won each of the players, find how many cities most likely to win Kosta in this move.

INPUT


In the first row are given four numbers: N - the number of cities (2 <= N <= 100 000), B1 - the number of conquered towns of Kosta, B2 - the number of conquered cities from Kiril (1 <= B1, B2 <= 100,000; B1 + B2 <= N), P - the number of coins that can be spent in Kosta's move (0 <= P <= 100 000).
In the second line are given B1 numbers, which indicate the city that has won Kosta.
In the third row given B2 numbers, which indicate the city that has won Kiril.
The fourth line has a number M (1 <= M <= min (200, 000, N * (N - 1) / 2)), the number of pairs of neighboring cities.
In each of the following M lines are given ordinal numbers of the two neighboring cities (cities are numbered with numbers from 1 to N)

OUTPUT
The first and only line print a number that indicates the maximum number of cities that can conquer Kosta with given number of coins.


EXAMPLES:
inp:
3 1 1 2
2
3
3
1 2
2 3
1 3
out: 1

inp:
5 1 1 2
2
3
4
1 2
1 3
3 4
1 5
out: 2
Time Limit:1 second
Memory Limit:64 MB

GUYS Help please :)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
  #include <iostream>
#include <vector>
using namespace std;

int main(){

int b1,b2,n,p;
cin >> n >> b1 >> b2 >> p ;
vector<int> kosta ;
kosta.resize(b1+p) ;
int kiril[b2] ;
for(int i=0;i<b1;i++){
    cin >> kosta[i] ;
}
for(int j=0;j<b2;j++){
    cin >> kiril[j] ;
}
int m,counter=0,x,y;
cin >> m;
for(int i=0;i<m;i++){
    cin >> x >> y ;
    for(int j=0;j<n;j++){
        if((x==kosta[j] && y!=kiril[j])){
                 for(int z=0;z<kosta.size();z++){
                if(y==kosta[z] && p!=0){
                    counter--;
                    break;
                }
            }
           if(p>0){
           counter++;
            p-- ;
            kosta.push_back(y);
        b1++ ;


           }

        }else if((x!=kiril[j] && y==kosta[j])){
            for(int c=0;c<kosta.size();c++){
                if(x==kosta[c] && p!=0){
            counter--;
            break;
                }
            }
             if(p>0){
           counter++;
            p-- ;
            kosta.push_back(x);



           }
           }
            if(p==0)
                i=m;
           }
        }

cout << counter;
return 0;
}

I stucked after 3 hours. Can someone help ? Please functional program that works even with N=100 000. Thanks :) .
Last edited on
Krenkov (2)
Please I need help this is hard task can someone help me please ? :) :)
Topic archived. No new replies allowed.