# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
960534 | 2024-04-10T15:28:19 Z | vjudge1 | Split the Attractions (IOI19_split) | C++17 | 2 ms | 5368 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; 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; } 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]); } vector<int> ans(n , 0); dfs(0); if(v == -1)return ans; 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 | 5208 KB | ok, correct split |
2 | Correct | 2 ms | 5208 KB | ok, correct split |
3 | Correct | 2 ms | 5212 KB | ok, correct split |
4 | Correct | 1 ms | 5212 KB | ok, correct split |
5 | Correct | 2 ms | 5368 KB | ok, correct split |
6 | Incorrect | 2 ms | 5208 KB | jury found a solution, contestant did not |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 5208 KB | invalid split: #1=0, #2=1, #3=2 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 5212 KB | invalid split: #1=1, #2=1, #3=3 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 5208 KB | ok, correct split |
2 | Correct | 2 ms | 5208 KB | ok, no valid answer |
3 | Correct | 2 ms | 5212 KB | ok, correct split |
4 | Incorrect | 1 ms | 5212 KB | invalid split: #1=1, #2=3, #3=7 |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 5208 KB | ok, correct split |
2 | Correct | 2 ms | 5208 KB | ok, correct split |
3 | Correct | 2 ms | 5212 KB | ok, correct split |
4 | Correct | 1 ms | 5212 KB | ok, correct split |
5 | Correct | 2 ms | 5368 KB | ok, correct split |
6 | Incorrect | 2 ms | 5208 KB | jury found a solution, contestant did not |
7 | Halted | 0 ms | 0 KB | - |