# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
591081 | 2022-07-06T20:17:38 Z | almothana05 | Split the Attractions (IOI19_split) | C++14 | 95 ms | 24176 KB |
#include "split.h" #include<bits/stdc++.h> #define mod 1000000007 using namespace std; vector<pair<int , int> >gru; vector<int> vis; vector<int>gr[500000]; int re , pl = -1 , maxi = mod , f[500000]; int dfs(int x){ int sub = 1; vis[x] = 1; for(int i = 0 ; i< gr[x].size() ; i ++){ int kind = gr[x][i]; if(vis[kind] == 0){ sub += dfs(kind); } else{ f[x] = kind; } } if(sub == gru[0].first + gru[1].first + gru[2].first ){ return 0; } if(sub >= gru[0].first && sub < maxi){ maxi = sub; pl = x; } return sub; } void dfs1(int x , int ins){ if(re <= 0){ return; } vis[x] = ins; re--; for(int i = 0 ; i < gr[x].size() ; i++){ int kind = gr[x][i]; if(kind != f[x] && vis[kind] == 0){ dfs1(kind , ins); } } } vector<int> find_split(int menge, int a, int b, int c, vector<int> p, vector<int> q) { int root; for(int i = 0 ;i < menge ; i++){ vis.push_back(0); } gru.push_back({a , 1}); gru.push_back({b , 2}); gru.push_back({c , 3}); sort(gru.begin() , gru.end()); for(int i = 0 ; i < p.size() ; i++){ gr[p[i]].push_back(q[i]); gr[q[i]].push_back(p[i]); } for(int i = 0 ; i < menge ; i++){ if(gr[i].size() > 1){ root = i; break; } } dfs(root); for(int i = 0 ; i < menge ; i++){ vis[i] = 0; } if(maxi == mod){ return vis; } re = gru[0].first; dfs1( pl , gru[0].second ); re = gru[1].first; dfs1(root , gru[1].second); if(re > 0){ // assert(re == 100000 - 78160); assert(maxi == 78160); for(int i = 0 ; i < menge ; i++){ vis[i] =0; } return vis; } for(int i = 0 ; i < menge ; i ++){ if(vis[i] == 0){ vis[i] = gru[2].second; } } return vis; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11988 KB | ok, correct split |
2 | Correct | 6 ms | 11988 KB | ok, correct split |
3 | Correct | 8 ms | 11988 KB | ok, correct split |
4 | Correct | 6 ms | 11988 KB | ok, correct split |
5 | Correct | 6 ms | 12044 KB | ok, correct split |
6 | Correct | 6 ms | 12012 KB | ok, correct split |
7 | Correct | 82 ms | 23824 KB | ok, correct split |
8 | Correct | 66 ms | 22068 KB | ok, correct split |
9 | Correct | 75 ms | 21380 KB | ok, correct split |
10 | Correct | 62 ms | 24176 KB | ok, correct split |
11 | Correct | 75 ms | 24096 KB | ok, correct split |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 11988 KB | ok, correct split |
2 | Correct | 7 ms | 11988 KB | ok, correct split |
3 | Correct | 6 ms | 11988 KB | ok, correct split |
4 | Correct | 85 ms | 21828 KB | ok, correct split |
5 | Correct | 62 ms | 17984 KB | ok, correct split |
6 | Correct | 69 ms | 24068 KB | ok, correct split |
7 | Correct | 75 ms | 21792 KB | ok, correct split |
8 | Correct | 95 ms | 20164 KB | ok, correct split |
9 | Correct | 65 ms | 17936 KB | ok, correct split |
10 | Correct | 59 ms | 18212 KB | ok, correct split |
11 | Correct | 46 ms | 18204 KB | ok, correct split |
12 | Correct | 48 ms | 18208 KB | ok, correct split |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 11988 KB | ok, correct split |
2 | Incorrect | 72 ms | 17988 KB | jury found a solution, contestant did not |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11928 KB | ok, correct split |
2 | Correct | 6 ms | 11944 KB | ok, no valid answer |
3 | Correct | 7 ms | 11972 KB | ok, correct split |
4 | Runtime error | 16 ms | 24156 KB | Execution killed with signal 6 |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11988 KB | ok, correct split |
2 | Correct | 6 ms | 11988 KB | ok, correct split |
3 | Correct | 8 ms | 11988 KB | ok, correct split |
4 | Correct | 6 ms | 11988 KB | ok, correct split |
5 | Correct | 6 ms | 12044 KB | ok, correct split |
6 | Correct | 6 ms | 12012 KB | ok, correct split |
7 | Correct | 82 ms | 23824 KB | ok, correct split |
8 | Correct | 66 ms | 22068 KB | ok, correct split |
9 | Correct | 75 ms | 21380 KB | ok, correct split |
10 | Correct | 62 ms | 24176 KB | ok, correct split |
11 | Correct | 75 ms | 24096 KB | ok, correct split |
12 | Correct | 8 ms | 11988 KB | ok, correct split |
13 | Correct | 7 ms | 11988 KB | ok, correct split |
14 | Correct | 6 ms | 11988 KB | ok, correct split |
15 | Correct | 85 ms | 21828 KB | ok, correct split |
16 | Correct | 62 ms | 17984 KB | ok, correct split |
17 | Correct | 69 ms | 24068 KB | ok, correct split |
18 | Correct | 75 ms | 21792 KB | ok, correct split |
19 | Correct | 95 ms | 20164 KB | ok, correct split |
20 | Correct | 65 ms | 17936 KB | ok, correct split |
21 | Correct | 59 ms | 18212 KB | ok, correct split |
22 | Correct | 46 ms | 18204 KB | ok, correct split |
23 | Correct | 48 ms | 18208 KB | ok, correct split |
24 | Correct | 7 ms | 11988 KB | ok, correct split |
25 | Incorrect | 72 ms | 17988 KB | jury found a solution, contestant did not |
26 | Halted | 0 ms | 0 KB | - |