# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
960537 | 2024-04-10T15:30:33 Z | vjudge1 | Split the Attractions (IOI19_split) | C++17 | 75 ms | 21588 KB |
#include "split.h" #include <bits/stdc++.h> #define ll long long using namespace std; #define pb push_back const int N = 1e5 + 10; vector<int> g1[N]; vector<int> g2[N]; int res[N]; bool vis[N]; int n; pair<int,int> f[3]; int v = -1; bool bb = false; int dfs(int x){ vis[x] = 1; int sz = 1; for(auto u : g1[x]){ if(!vis[u]){ sz += dfs(u); g2[x].pb(u); } } if(v != -1)return sz; if(sz >= f[0].first && n - sz >= f[1].first){ v = x; } if(sz >= f[1].first && n - sz >= f[0].first){ v = x; bb = true; } return sz; } void dfsa(int x){ if(!f[0].first)return; res[x] = f[0].second; f[0].first--; for(auto u : g2[x]){ if(!res[u]){ dfsa(u); } } } void dfsb(int x){ if(!f[1].first)return; res[x] = f[1].second; f[1].first--; for(auto u : g2[x]){ if(!res[u]){ dfsb(u); } } } vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) { n = nn; f[0] = {a, 1}; f[1] = {b, 2}; f[2] = {c, 3}; sort(f, f + 3); for(int i = 0;i<p.size();i++){ g1[p[i]].pb(q[i]); g1[q[i]].pb(p[i]); } vector<int> ans(n , 0); dfs(0); if(v == -1)return ans; if(bb){ dfsb(v); dfsa(0); }else{ dfsa(v); dfsb(0); } for(int i = 0;i<n;i++){ if(!res[i])res[i] =f[2].second; ans[i] = res[i]; } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 5212 KB | ok, correct split |
2 | Correct | 2 ms | 5212 KB | ok, correct split |
3 | Correct | 2 ms | 5212 KB | ok, correct split |
4 | Correct | 1 ms | 5212 KB | ok, correct split |
5 | Correct | 1 ms | 5212 KB | ok, correct split |
6 | Correct | 2 ms | 5468 KB | ok, correct split |
7 | Correct | 51 ms | 21084 KB | ok, correct split |
8 | Correct | 71 ms | 18960 KB | ok, correct split |
9 | Correct | 52 ms | 18288 KB | ok, correct split |
10 | Correct | 57 ms | 21536 KB | ok, correct split |
11 | Correct | 55 ms | 21588 KB | ok, correct split |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 5208 KB | ok, correct split |
2 | Correct | 2 ms | 5212 KB | ok, correct split |
3 | Correct | 2 ms | 5212 KB | ok, correct split |
4 | Correct | 60 ms | 17384 KB | ok, correct split |
5 | Correct | 44 ms | 12380 KB | ok, correct split |
6 | Correct | 57 ms | 21588 KB | ok, correct split |
7 | Correct | 50 ms | 18768 KB | ok, correct split |
8 | Correct | 75 ms | 14928 KB | ok, correct split |
9 | Correct | 44 ms | 13916 KB | ok, correct split |
10 | Correct | 31 ms | 11728 KB | ok, correct split |
11 | Correct | 44 ms | 11764 KB | ok, correct split |
12 | Correct | 33 ms | 11732 KB | ok, correct split |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 5208 KB | ok, correct split |
2 | Correct | 43 ms | 12368 KB | ok, correct split |
3 | Correct | 19 ms | 8796 KB | ok, correct split |
4 | Correct | 1 ms | 5212 KB | ok, correct split |
5 | Correct | 49 ms | 17608 KB | ok, correct split |
6 | Correct | 48 ms | 17240 KB | ok, correct split |
7 | Correct | 48 ms | 16976 KB | ok, correct split |
8 | Correct | 75 ms | 18640 KB | ok, correct split |
9 | Correct | 50 ms | 16976 KB | ok, correct split |
10 | Correct | 14 ms | 8028 KB | ok, no valid answer |
11 | Correct | 21 ms | 9296 KB | ok, no valid answer |
12 | Correct | 41 ms | 12748 KB | ok, no valid answer |
13 | Correct | 47 ms | 13396 KB | ok, no valid answer |
14 | Correct | 32 ms | 12756 KB | ok, no valid answer |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 5212 KB | ok, correct split |
2 | Correct | 1 ms | 5212 KB | ok, no valid answer |
3 | Correct | 2 ms | 5212 KB | ok, correct split |
4 | Correct | 2 ms | 5212 KB | ok, correct split |
5 | Correct | 1 ms | 5212 KB | ok, correct split |
6 | Correct | 1 ms | 5208 KB | ok, correct split |
7 | Correct | 2 ms | 5212 KB | ok, correct split |
8 | Correct | 2 ms | 5408 KB | ok, correct split |
9 | Correct | 4 ms | 5724 KB | ok, correct split |
10 | Correct | 3 ms | 5468 KB | ok, correct split |
11 | Correct | 2 ms | 5468 KB | ok, correct split |
12 | Correct | 4 ms | 5468 KB | ok, correct split |
13 | Correct | 1 ms | 5212 KB | ok, correct split |
14 | Correct | 1 ms | 5212 KB | ok, correct split |
15 | Correct | 2 ms | 5212 KB | ok, correct split |
16 | Correct | 2 ms | 5212 KB | ok, correct split |
17 | Correct | 1 ms | 5212 KB | ok, correct split |
18 | Correct | 1 ms | 5212 KB | ok, correct split |
19 | Correct | 2 ms | 5464 KB | ok, correct split |
20 | Correct | 2 ms | 5468 KB | ok, correct split |
21 | Correct | 3 ms | 5720 KB | ok, correct split |
22 | Correct | 3 ms | 5468 KB | ok, correct split |
23 | Correct | 3 ms | 5724 KB | ok, correct split |
24 | Correct | 2 ms | 5976 KB | ok, correct split |
25 | Correct | 2 ms | 5724 KB | ok, correct split |
26 | Incorrect | 3 ms | 5468 KB | jury found a solution, contestant did not |
27 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 5212 KB | ok, correct split |
2 | Correct | 2 ms | 5212 KB | ok, correct split |
3 | Correct | 2 ms | 5212 KB | ok, correct split |
4 | Correct | 1 ms | 5212 KB | ok, correct split |
5 | Correct | 1 ms | 5212 KB | ok, correct split |
6 | Correct | 2 ms | 5468 KB | ok, correct split |
7 | Correct | 51 ms | 21084 KB | ok, correct split |
8 | Correct | 71 ms | 18960 KB | ok, correct split |
9 | Correct | 52 ms | 18288 KB | ok, correct split |
10 | Correct | 57 ms | 21536 KB | ok, correct split |
11 | Correct | 55 ms | 21588 KB | ok, correct split |
12 | Correct | 1 ms | 5208 KB | ok, correct split |
13 | Correct | 2 ms | 5212 KB | ok, correct split |
14 | Correct | 2 ms | 5212 KB | ok, correct split |
15 | Correct | 60 ms | 17384 KB | ok, correct split |
16 | Correct | 44 ms | 12380 KB | ok, correct split |
17 | Correct | 57 ms | 21588 KB | ok, correct split |
18 | Correct | 50 ms | 18768 KB | ok, correct split |
19 | Correct | 75 ms | 14928 KB | ok, correct split |
20 | Correct | 44 ms | 13916 KB | ok, correct split |
21 | Correct | 31 ms | 11728 KB | ok, correct split |
22 | Correct | 44 ms | 11764 KB | ok, correct split |
23 | Correct | 33 ms | 11732 KB | ok, correct split |
24 | Correct | 1 ms | 5208 KB | ok, correct split |
25 | Correct | 43 ms | 12368 KB | ok, correct split |
26 | Correct | 19 ms | 8796 KB | ok, correct split |
27 | Correct | 1 ms | 5212 KB | ok, correct split |
28 | Correct | 49 ms | 17608 KB | ok, correct split |
29 | Correct | 48 ms | 17240 KB | ok, correct split |
30 | Correct | 48 ms | 16976 KB | ok, correct split |
31 | Correct | 75 ms | 18640 KB | ok, correct split |
32 | Correct | 50 ms | 16976 KB | ok, correct split |
33 | Correct | 14 ms | 8028 KB | ok, no valid answer |
34 | Correct | 21 ms | 9296 KB | ok, no valid answer |
35 | Correct | 41 ms | 12748 KB | ok, no valid answer |
36 | Correct | 47 ms | 13396 KB | ok, no valid answer |
37 | Correct | 32 ms | 12756 KB | ok, no valid answer |
38 | Correct | 2 ms | 5212 KB | ok, correct split |
39 | Correct | 1 ms | 5212 KB | ok, no valid answer |
40 | Correct | 2 ms | 5212 KB | ok, correct split |
41 | Correct | 2 ms | 5212 KB | ok, correct split |
42 | Correct | 1 ms | 5212 KB | ok, correct split |
43 | Correct | 1 ms | 5208 KB | ok, correct split |
44 | Correct | 2 ms | 5212 KB | ok, correct split |
45 | Correct | 2 ms | 5408 KB | ok, correct split |
46 | Correct | 4 ms | 5724 KB | ok, correct split |
47 | Correct | 3 ms | 5468 KB | ok, correct split |
48 | Correct | 2 ms | 5468 KB | ok, correct split |
49 | Correct | 4 ms | 5468 KB | ok, correct split |
50 | Correct | 1 ms | 5212 KB | ok, correct split |
51 | Correct | 1 ms | 5212 KB | ok, correct split |
52 | Correct | 2 ms | 5212 KB | ok, correct split |
53 | Correct | 2 ms | 5212 KB | ok, correct split |
54 | Correct | 1 ms | 5212 KB | ok, correct split |
55 | Correct | 1 ms | 5212 KB | ok, correct split |
56 | Correct | 2 ms | 5464 KB | ok, correct split |
57 | Correct | 2 ms | 5468 KB | ok, correct split |
58 | Correct | 3 ms | 5720 KB | ok, correct split |
59 | Correct | 3 ms | 5468 KB | ok, correct split |
60 | Correct | 3 ms | 5724 KB | ok, correct split |
61 | Correct | 2 ms | 5976 KB | ok, correct split |
62 | Correct | 2 ms | 5724 KB | ok, correct split |
63 | Incorrect | 3 ms | 5468 KB | jury found a solution, contestant did not |
64 | Halted | 0 ms | 0 KB | - |