# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
152071 | 2019-09-06T08:25:17 Z | oolimry | Split the Attractions (IOI19_split) | C++14 | 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
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 | - |
# | 결과 | 실행 시간 | 메모리 | 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 | - |