oj.uz

Submission #162582

# Submission time Handle Problem Language Result Execution time Memory
162582 2019-11-08T20:14:21 Z MvC Political Development (BOI17_politicaldevelopment) C++11
100 / 100
 886 ms 314992 KB 
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long lint;
    typedef pair<int, int> pi;
     
    vector<int> gph[50005];
    set<pi> edgs;
    bool vis[50005];
    int deg[50005];
    int n;
    bitset<50005>b[50005];
    int main(){
    	scanf("%d %*d",&n);
    	priority_queue<pi, vector<pi>, greater<pi> > pq;
    	for(int i=0; i<n; i++){
    		scanf("%d",&deg[i]);
    		gph[i].resize(deg[i]);
    		pq.push(pi(deg[i], i));
    		for(auto &j : gph[i]){
    			scanf("%d",&j);
    			b[i][j]=1;
    		}
    	}
    	int ans = 0;
    	while(true){
    		while(!pq.empty() && vis[pq.top().second]) pq.pop();
    		if(pq.empty()) break;
    		int w = pq.top().second;
    		vis[w] = 1;
    		deg[w] = 0;
    		pq.pop();
    		vector<int> v = {w};
    		for(auto &j : gph[w]){
    			if(!vis[j]){
    				deg[j]--;
    				pq.push(pi(deg[j], j));
    				v.push_back(j);
    			}
    		}
    		vis[w] = 1;
    		bool adj[11][11] = {};
    		for(int i=0; i<v.size(); i++){
    			adj[i][i] = 1;
    			for(int j=0; j<v.size(); j++){
    				if(i != j && b[v[i]][v[j]]){
    					adj[i][j] = 1;
    				}
    			}
    		}
    		for(int i=1; i<(1<<v.size()); i+=2){
    			bool ok = 1;
    			int cnt = 0;
    			for(int j=0; j<v.size(); j++){
    				if((i >> j) % 2 == 0) continue;
    				cnt++;
    				for(int k=0; k<v.size(); k++){
    					if((i >> k) % 2 == 0) continue;
    					if(adj[j][k] == 0) ok = 0;
    				}
    			}
    			if(ok) ans = max(ans, cnt);
    		}
    	}
    	cout << ans;
    }

Compilation message

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:42:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0; i<v.size(); i++){
                    ~^~~~~~~~~
politicaldevelopment.cpp:44:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int j=0; j<v.size(); j++){
                     ~^~~~~~~~~
politicaldevelopment.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int j=0; j<v.size(); j++){
                     ~^~~~~~~~~
politicaldevelopment.cpp:56:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int k=0; k<v.size(); k++){
                      ~^~~~~~~~~
politicaldevelopment.cpp:13:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d %*d",&n);
      ~~~~~^~~~~~~~~~~~~
politicaldevelopment.cpp:16:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d",&deg[i]);
       ~~~~~^~~~~~~~~~~~~~
politicaldevelopment.cpp:20:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
        scanf("%d",&j);
        ~~~~~^~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 26 ms 22524 KB Output is correct
4 Correct 22 ms 21880 KB Output is correct
5 Correct 24 ms 21880 KB Output is correct
6 Correct 23 ms 21796 KB Output is correct
7 Correct 23 ms 22008 KB Output is correct
8 Correct 4 ms 1656 KB Output is correct
9 Correct 3 ms 1576 KB Output is correct
10 Correct 4 ms 1660 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 26 ms 22524 KB Output is correct
4 Correct 22 ms 21880 KB Output is correct
5 Correct 24 ms 21880 KB Output is correct
6 Correct 23 ms 21796 KB Output is correct
7 Correct 23 ms 22008 KB Output is correct
8 Correct 4 ms 1656 KB Output is correct
9 Correct 3 ms 1576 KB Output is correct
10 Correct 4 ms 1660 KB Output is correct
11 Correct 22 ms 21880 KB Output is correct
12 Correct 22 ms 21824 KB Output is correct
13 Correct 3 ms 1528 KB Output is correct
14 Correct 21 ms 21880 KB Output is correct
15 Correct 3 ms 1528 KB Output is correct
16 Correct 22 ms 21880 KB Output is correct
17 Correct 3 ms 1528 KB Output is correct
18 Correct 23 ms 21880 KB Output is correct
19 Correct 8 ms 1656 KB Output is correct
20 Correct 22 ms 21752 KB Output is correct
21 Correct 22 ms 21752 KB Output is correct
22 Correct 4 ms 1656 KB Output is correct
23 Correct 25 ms 22920 KB Output is correct
24 Correct 4 ms 1656 KB Output is correct
25 Correct 25 ms 22936 KB Output is correct
26 Correct 24 ms 22136 KB Output is correct
27 Correct 24 ms 22776 KB Output is correct
28 Correct 24 ms 22136 KB Output is correct
29 Correct 23 ms 22776 KB Output is correct
30 Correct 24 ms 22652 KB Output is correct
31 Correct 25 ms 23032 KB Output is correct
32 Correct 25 ms 22776 KB Output is correct
33 Correct 25 ms 23160 KB Output is correct
34 Correct 26 ms 23032 KB Output is correct
35 Correct 13 ms 11896 KB Output is correct
36 Correct 19 ms 12024 KB Output is correct
37 Correct 14 ms 12024 KB Output is correct
38 Correct 8 ms 6648 KB Output is correct
39 Correct 8 ms 6648 KB Output is correct
40 Correct 29 ms 23544 KB Output is correct
41 Correct 8 ms 6648 KB Output is correct
42 Correct 30 ms 23516 KB Output is correct
43 Correct 27 ms 23544 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1656 KB Output is correct
2 Correct 3 ms 1656 KB Output is correct
3 Correct 4 ms 1656 KB Output is correct
4 Correct 3 ms 1528 KB Output is correct
5 Correct 3 ms 1528 KB Output is correct
6 Correct 3 ms 1656 KB Output is correct
7 Correct 3 ms 1656 KB Output is correct
8 Correct 3 ms 1528 KB Output is correct
9 Correct 3 ms 1656 KB Output is correct
10 Correct 3 ms 1532 KB Output is correct
11 Correct 597 ms 313576 KB Output is correct
12 Correct 3 ms 1528 KB Output is correct
13 Correct 570 ms 313552 KB Output is correct
14 Correct 3 ms 1528 KB Output is correct
15 Correct 562 ms 314692 KB Output is correct
16 Correct 565 ms 314992 KB Output is correct
17 Correct 569 ms 314728 KB Output is correct
18 Correct 575 ms 314764 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 26 ms 22524 KB Output is correct
4 Correct 22 ms 21880 KB Output is correct
5 Correct 24 ms 21880 KB Output is correct
6 Correct 23 ms 21796 KB Output is correct
7 Correct 23 ms 22008 KB Output is correct
8 Correct 4 ms 1656 KB Output is correct
9 Correct 3 ms 1576 KB Output is correct
10 Correct 4 ms 1660 KB Output is correct
11 Correct 22 ms 21880 KB Output is correct
12 Correct 22 ms 21824 KB Output is correct
13 Correct 3 ms 1528 KB Output is correct
14 Correct 21 ms 21880 KB Output is correct
15 Correct 3 ms 1528 KB Output is correct
16 Correct 22 ms 21880 KB Output is correct
17 Correct 3 ms 1528 KB Output is correct
18 Correct 23 ms 21880 KB Output is correct
19 Correct 8 ms 1656 KB Output is correct
20 Correct 22 ms 21752 KB Output is correct
21 Correct 22 ms 21752 KB Output is correct
22 Correct 4 ms 1656 KB Output is correct
23 Correct 25 ms 22920 KB Output is correct
24 Correct 4 ms 1656 KB Output is correct
25 Correct 25 ms 22936 KB Output is correct
26 Correct 24 ms 22136 KB Output is correct
27 Correct 24 ms 22776 KB Output is correct
28 Correct 24 ms 22136 KB Output is correct
29 Correct 23 ms 22776 KB Output is correct
30 Correct 24 ms 22652 KB Output is correct
31 Correct 25 ms 23032 KB Output is correct
32 Correct 25 ms 22776 KB Output is correct
33 Correct 25 ms 23160 KB Output is correct
34 Correct 26 ms 23032 KB Output is correct
35 Correct 13 ms 11896 KB Output is correct
36 Correct 19 ms 12024 KB Output is correct
37 Correct 14 ms 12024 KB Output is correct
38 Correct 8 ms 6648 KB Output is correct
39 Correct 8 ms 6648 KB Output is correct
40 Correct 29 ms 23544 KB Output is correct
41 Correct 8 ms 6648 KB Output is correct
42 Correct 30 ms 23516 KB Output is correct
43 Correct 27 ms 23544 KB Output is correct
44 Correct 88 ms 24260 KB Output is correct
45 Correct 3 ms 1528 KB Output is correct
46 Correct 27 ms 23388 KB Output is correct
47 Correct 35 ms 24540 KB Output is correct
48 Correct 27 ms 23544 KB Output is correct
49 Correct 36 ms 24568 KB Output is correct
50 Correct 37 ms 24388 KB Output is correct
51 Correct 297 ms 25332 KB Output is correct
52 Correct 23 ms 21880 KB Output is correct
53 Correct 886 ms 25852 KB Output is correct
54 Correct 668 ms 25844 KB Output is correct
55 Correct 35 ms 21880 KB Output is correct
56 Correct 23 ms 21880 KB Output is correct
57 Correct 4 ms 1656 KB Output is correct
58 Correct 671 ms 25632 KB Output is correct
59 Correct 27 ms 23800 KB Output is correct
60 Correct 24 ms 21908 KB Output is correct
61 Correct 26 ms 23676 KB Output is correct
62 Correct 27 ms 23672 KB Output is correct
63 Correct 91 ms 24568 KB Output is correct
64 Correct 50 ms 24356 KB Output is correct
65 Correct 26 ms 23420 KB Output is correct
66 Correct 27 ms 23800 KB Output is correct
67 Correct 62 ms 24696 KB Output is correct
68 Correct 50 ms 24312 KB Output is correct
69 Correct 27 ms 23416 KB Output is correct
70 Correct 78 ms 24312 KB Output is correct
71 Correct 61 ms 24576 KB Output is correct
72 Correct 48 ms 24800 KB Output is correct
73 Correct 23 ms 22904 KB Output is correct
74 Correct 34 ms 24184 KB Output is correct
75 Correct 49 ms 24700 KB Output is correct
76 Correct 30 ms 24056 KB Output is correct
77 Correct 111 ms 24952 KB Output is correct
78 Correct 23 ms 22780 KB Output is correct
79 Correct 54 ms 12664 KB Output is correct
80 Correct 30 ms 24056 KB Output is correct
81 Correct 112 ms 24952 KB Output is correct
82 Correct 8 ms 6648 KB Output is correct
83 Correct 56 ms 12796 KB Output is correct
84 Correct 108 ms 24824 KB Output is correct
85 Correct 8 ms 6648 KB Output is correct
86 Correct 50 ms 24824 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 26 ms 22524 KB Output is correct
4 Correct 22 ms 21880 KB Output is correct
5 Correct 24 ms 21880 KB Output is correct
6 Correct 23 ms 21796 KB Output is correct
7 Correct 23 ms 22008 KB Output is correct
8 Correct 4 ms 1656 KB Output is correct
9 Correct 3 ms 1576 KB Output is correct
10 Correct 4 ms 1660 KB Output is correct
11 Correct 22 ms 21880 KB Output is correct
12 Correct 22 ms 21824 KB Output is correct
13 Correct 3 ms 1528 KB Output is correct
14 Correct 21 ms 21880 KB Output is correct
15 Correct 3 ms 1528 KB Output is correct
16 Correct 22 ms 21880 KB Output is correct
17 Correct 3 ms 1528 KB Output is correct
18 Correct 23 ms 21880 KB Output is correct
19 Correct 8 ms 1656 KB Output is correct
20 Correct 22 ms 21752 KB Output is correct
21 Correct 22 ms 21752 KB Output is correct
22 Correct 4 ms 1656 KB Output is correct
23 Correct 25 ms 22920 KB Output is correct
24 Correct 4 ms 1656 KB Output is correct
25 Correct 25 ms 22936 KB Output is correct
26 Correct 24 ms 22136 KB Output is correct
27 Correct 24 ms 22776 KB Output is correct
28 Correct 24 ms 22136 KB Output is correct
29 Correct 23 ms 22776 KB Output is correct
30 Correct 24 ms 22652 KB Output is correct
31 Correct 25 ms 23032 KB Output is correct
32 Correct 25 ms 22776 KB Output is correct
33 Correct 25 ms 23160 KB Output is correct
34 Correct 26 ms 23032 KB Output is correct
35 Correct 13 ms 11896 KB Output is correct
36 Correct 19 ms 12024 KB Output is correct
37 Correct 14 ms 12024 KB Output is correct
38 Correct 8 ms 6648 KB Output is correct
39 Correct 8 ms 6648 KB Output is correct
40 Correct 29 ms 23544 KB Output is correct
41 Correct 8 ms 6648 KB Output is correct
42 Correct 30 ms 23516 KB Output is correct
43 Correct 27 ms 23544 KB Output is correct
44 Correct 3 ms 1528 KB Output is correct
45 Correct 369 ms 306952 KB Output is correct
46 Correct 292 ms 278288 KB Output is correct
47 Correct 373 ms 306408 KB Output is correct
48 Correct 361 ms 307408 KB Output is correct
49 Correct 198 ms 205240 KB Output is correct
50 Correct 466 ms 313712 KB Output is correct
51 Correct 366 ms 305516 KB Output is correct
52 Correct 193 ms 191980 KB Output is correct
53 Correct 198 ms 205168 KB Output is correct
54 Correct 16 ms 2420 KB Output is correct
55 Correct 362 ms 312940 KB Output is correct
56 Correct 186 ms 190320 KB Output is correct
57 Correct 196 ms 192868 KB Output is correct
58 Correct 280 ms 291184 KB Output is correct
59 Correct 182 ms 190704 KB Output is correct
60 Correct 184 ms 190832 KB Output is correct
61 Correct 281 ms 291056 KB Output is correct
62 Correct 242 ms 262636 KB Output is correct
63 Correct 376 ms 286076 KB Output is correct
64 Correct 189 ms 190520 KB Output is correct
65 Correct 321 ms 296304 KB Output is correct
66 Correct 250 ms 263152 KB Output is correct
67 Correct 306 ms 285780 KB Output is correct
68 Correct 331 ms 294640 KB Output is correct
69 Correct 333 ms 295316 KB Output is correct
70 Correct 248 ms 263024 KB Output is correct
71 Correct 330 ms 294256 KB Output is correct
72 Correct 320 ms 276852 KB Output is correct
73 Correct 346 ms 306804 KB Output is correct
74 Correct 250 ms 263232 KB Output is correct
75 Correct 154 ms 143860 KB Output is correct
76 Correct 287 ms 269332 KB Output is correct
77 Correct 352 ms 307132 KB Output is correct
78 Correct 174 ms 149108 KB Output is correct
79 Correct 153 ms 143860 KB Output is correct
80 Correct 70 ms 59128 KB Output is correct
81 Correct 173 ms 149364 KB Output is correct
82 Correct 319 ms 303216 KB Output is correct
83 Correct 65 ms 59256 KB Output is correct
84 Correct 437 ms 302680 KB Output is correct