oj.uz

Submission #152071

# Submission time Handle Problem Language Result Execution time Memory
152071 2019-09-06T08:25:17 Z oolimry Split the Attractions (IOI19_split) C++14
40 / 100
 132 ms 14324 KB 
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> ii;
vi adj[100005];
int dp[100005];
bool vis[100005];
void dfs(int u){
	vis[u] = true;
	for(int i = 0;i < adj[u].size();i++){
		int v = adj[u][i];
		if(!vis[v]){
			dfs(v);
			dp[u] += dp[v];
		}
	}
	dp[u] += 1;
}
vi find_split(int n, int aaa, int bbb, int ccc, vi p, vi q) {
	for(int i = 0;i < p.size();i++){
		int x = p[i];
		int y = q[i];
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	
	dfs(0);
	
	vector<pair<int,int> > vv;
	vv.push_back(ii(aaa,1));
	vv.push_back(ii(bbb,2));
	vv.push_back(ii(ccc,3));
	sort(vv.begin(),vv.end());
	int a = vv[0].first;
	int b = vv[1].first;
	for(int i = 0;i < p.size();i++){
		int x = p[i];
		int y = q[i];
		
		
		int l, r;
		int xx, yy;
		if(dp[y] > dp[x]){
			if(dp[0] - dp[x] > dp[x]){
				l = dp[x];
				r = dp[0] - dp[x];
				xx = x; yy = y;
			}
			else{
				r = dp[x];
				l = dp[0] - dp[x];
				xx = y; yy = x;
			}
		}
		else{
			if(dp[0] - dp[y] > dp[y]){
				l = dp[y];
				r = dp[0] - dp[y];
				xx = y; yy = x;
			}
			else{
				r = dp[y];
				l = dp[0] - dp[y];
				xx = x; yy = y;
			}
		}
		if(l >= a && r >= b){
			queue<int> bfs;
			
			//cout << ll << " " << rr << "\n";
			vi vis;
			for(int i = 0;i < n;i++) vis.push_back(vv[2].second);
			//vis[x] = vv[0].second;
			//vis[y] = vv[1].second;

			bfs.push(xx);
			
			int cnt = a;
			while(!bfs.empty()){
				int u = bfs.front();
				bfs.pop();
				
				if(vis[u] != vv[2].second) continue;
				vis[u] = vv[0].second;
				cnt--;
				if(cnt == 0) break;
				for(int j = 0;j < adj[u].size();j++){
					int v = adj[u][j];
					if(v == x || v == y) continue;
					bfs.push(v);
				}
			}
			
			while(!bfs.empty()) bfs.pop();
			bfs.push(yy);
			
			cnt = b;
			while(!bfs.empty()){
				int u = bfs.front();
				bfs.pop();
				
				if(vis[u] != vv[2].second) continue;
				vis[u] = vv[1].second;
				cnt--;
				if(cnt == 0) break;
				for(int j = 0;j < adj[u].size();j++){
					int v = adj[u][j];
					if(v == x || v == y) continue;
					bfs.push(v);
				}
			}
			return vis;
		}
	}
	vi none;
	for(int i = 0;i < n;i++) none.push_back(0);
	return none;
}

Compilation message

split.cpp: In function 'void dfs(int)':
split.cpp:12:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i < adj[u].size();i++){
                ~~^~~~~~~~~~~~~~~
split.cpp: In function 'vi find_split(int, int, int, int, vi, vi)':
split.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i < p.size();i++){
                ~~^~~~~~~~~~
split.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i < p.size();i++){
                ~~^~~~~~~~~~
split.cpp:89:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0;j < adj[u].size();j++){
                   ~~^~~~~~~~~~~~~~~
split.cpp:108:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0;j < adj[u].size();j++){
                   ~~^~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2808 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 4 ms 2680 KB ok, correct split
6 Correct 4 ms 2680 KB ok, correct split
7 Correct 93 ms 13016 KB ok, correct split
8 Correct 103 ms 11644 KB ok, correct split
9 Correct 94 ms 11212 KB ok, correct split
10 Correct 96 ms 14324 KB ok, correct split
11 Correct 102 ms 14324 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 113 ms 11736 KB ok, correct split
5 Correct 84 ms 8696 KB ok, correct split
6 Correct 123 ms 13172 KB ok, correct split
7 Correct 105 ms 11424 KB ok, correct split
8 Correct 132 ms 10992 KB ok, correct split
9 Correct 100 ms 8632 KB ok, correct split
10 Correct 62 ms 9072 KB ok, correct split
11 Correct 64 ms 9072 KB ok, correct split
12 Correct 65 ms 10224 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 82 ms 9808 KB ok, correct split
3 Correct 31 ms 5624 KB ok, correct split
4 Correct 4 ms 2808 KB ok, correct split
5 Correct 98 ms 11256 KB ok, correct split
6 Correct 89 ms 11040 KB ok, correct split
7 Correct 96 ms 10996 KB ok, correct split
8 Correct 94 ms 11796 KB ok, correct split
9 Correct 130 ms 10868 KB ok, correct split
10 Correct 27 ms 5244 KB ok, no valid answer
11 Correct 39 ms 6264 KB ok, no valid answer
12 Correct 72 ms 10100 KB ok, no valid answer
13 Correct 80 ms 9848 KB ok, no valid answer
14 Correct 65 ms 10224 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB ok, correct split
2 Correct 5 ms 2680 KB ok, no valid answer
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 4 ms 2680 KB ok, correct split
6 Correct 4 ms 2680 KB ok, correct split
7 Correct 4 ms 2680 KB ok, correct split
8 Correct 4 ms 2680 KB ok, correct split
9 Correct 6 ms 2936 KB ok, correct split
10 Correct 7 ms 2936 KB ok, correct split
11 Correct 4 ms 2680 KB ok, correct split
12 Incorrect 6 ms 2936 KB invalid split: #1=800, #2=1468, #3=133
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2808 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 4 ms 2680 KB ok, correct split
6 Correct 4 ms 2680 KB ok, correct split
7 Correct 93 ms 13016 KB ok, correct split
8 Correct 103 ms 11644 KB ok, correct split
9 Correct 94 ms 11212 KB ok, correct split
10 Correct 96 ms 14324 KB ok, correct split
11 Correct 102 ms 14324 KB ok, correct split
12 Correct 4 ms 2680 KB ok, correct split
13 Correct 4 ms 2680 KB ok, correct split
14 Correct 4 ms 2680 KB ok, correct split
15 Correct 113 ms 11736 KB ok, correct split
16 Correct 84 ms 8696 KB ok, correct split
17 Correct 123 ms 13172 KB ok, correct split
18 Correct 105 ms 11424 KB ok, correct split
19 Correct 132 ms 10992 KB ok, correct split
20 Correct 100 ms 8632 KB ok, correct split
21 Correct 62 ms 9072 KB ok, correct split
22 Correct 64 ms 9072 KB ok, correct split
23 Correct 65 ms 10224 KB ok, correct split
24 Correct 4 ms 2680 KB ok, correct split
25 Correct 82 ms 9808 KB ok, correct split
26 Correct 31 ms 5624 KB ok, correct split
27 Correct 4 ms 2808 KB ok, correct split
28 Correct 98 ms 11256 KB ok, correct split
29 Correct 89 ms 11040 KB ok, correct split
30 Correct 96 ms 10996 KB ok, correct split
31 Correct 94 ms 11796 KB ok, correct split
32 Correct 130 ms 10868 KB ok, correct split
33 Correct 27 ms 5244 KB ok, no valid answer
34 Correct 39 ms 6264 KB ok, no valid answer
35 Correct 72 ms 10100 KB ok, no valid answer
36 Correct 80 ms 9848 KB ok, no valid answer
37 Correct 65 ms 10224 KB ok, no valid answer
38 Correct 5 ms 2680 KB ok, correct split
39 Correct 5 ms 2680 KB ok, no valid answer
40 Correct 4 ms 2680 KB ok, correct split
41 Correct 4 ms 2680 KB ok, correct split
42 Correct 4 ms 2680 KB ok, correct split
43 Correct 4 ms 2680 KB ok, correct split
44 Correct 4 ms 2680 KB ok, correct split
45 Correct 4 ms 2680 KB ok, correct split
46 Correct 6 ms 2936 KB ok, correct split
47 Correct 7 ms 2936 KB ok, correct split
48 Correct 4 ms 2680 KB ok, correct split
49 Incorrect 6 ms 2936 KB invalid split: #1=800, #2=1468, #3=133
50 Halted 0 ms 0 KB -