# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
169929 | 2019-12-23T09:43:04 Z | socho | Split the Attractions (IOI19_split) | C++14 | 1078 ms | 1048580 KB |
#include "bits/stdc++.h" #include "split.h" using namespace std; int N; const int MXN = 100005; int stsize[MXN]; vector<int> adj[MXN]; int parent[MXN]; bool blocked[MXN]; int dfs_st(int node, int last) { int sz = 1; parent[node] = last; for (int i=0; i<adj[node].size(); i++) { int ot = adj[node][i]; if (ot == last) continue; sz += dfs_st(ot, node); } return stsize[node] = sz; } int dfs_ce(int node, int last) { // cout << " > " << node << ' ' << stsize[node] << endl; for (int i=0; i<adj[node].size(); i++) { int ot = adj[node][i]; if (ot == last) continue; if (stsize[ot] * 2 > N) return dfs_ce(ot, node); } return node; } int get_centroid() { dfs_st(0, -1); return dfs_ce(0, -1); } int limit = 0; int taken = 0; vector<int> picked; void getst(int node) { if (taken >= limit) return; picked.push_back(node); blocked[node] = true; taken++; for (int i=0; i<adj[node].size(); i++) { if (adj[node][i] == parent[i]) continue; getst(adj[node][i]); } } vector<int> took; void travel(int node, int last) { if (taken >= limit) return; took.push_back(node); blocked[node] = true; taken++; for (int i=0; i<adj[node].size(); i++) { int ot = adj[node][i]; if (ot == last) continue; if (blocked[ot]) continue; travel(ot, node); } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { N = n; for (int i=0; i<p.size(); i++) { adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]); } int cen = get_centroid(); dfs_st(cen, -1); int vs[3] = {a, b, c}; sort(vs, vs+3); int smallest = vs[0]; int lowlabel, midlabel, highlabel; if (smallest == a) { lowlabel = 1; if (b > c) { midlabel = 3; highlabel = 2; } else { midlabel = 2; highlabel = 3; } } else if (smallest == b) { lowlabel = 2; if (a > c) { midlabel = 3; highlabel = 1; } else { midlabel = 1; highlabel = 3; } } else { lowlabel = 3; if (a > b) { midlabel = 2; highlabel = 1; } else { midlabel = 1; highlabel = 2; } } int where = cen; for (int i=0; i<n; i++) { if (stsize[i] >= smallest) { if (stsize[i] <= stsize[where]) { where = i; } } } int take = n - stsize[where]; if (vs[1] > take) { vector<int> res; for (int i=0; i<n; i++) res.push_back(0); return res; } vector<int> res(n, 0); limit = smallest; taken = 0; memset(blocked, 0, sizeof blocked); getst(where); for (int i=0; i<picked.size(); i++) { res[picked[i]] = lowlabel; } limit = vs[1]; taken = 0; travel(parent[where], where); for (int i=0; i<took.size(); i++) { res[took[i]] = midlabel; } for (int i=0; i<n; i++) { if (res[i] == 0) res[i] = highlabel; } return res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2808 KB | ok, correct split |
2 | Runtime error | 1078 ms | 1048576 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2808 KB | ok, correct split |
2 | Runtime error | 930 ms | 1048580 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2808 KB | ok, correct split |
2 | Incorrect | 87 ms | 11080 KB | invalid split: #1=3, #2=40000, #3=59997 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 907 ms | 1048576 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2808 KB | ok, correct split |
2 | Runtime error | 1078 ms | 1048576 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
3 | Halted | 0 ms | 0 KB | - |