# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
169935 | 2019-12-23T10:32:11 Z | socho | Split the Attractions (IOI19_split) | C++14 | 8 ms | 5752 KB |
#include "bits/stdc++.h" #include "split.h" using namespace std; int A, B, C, N; const int MXN = 100005; vector<int> adj[MXN]; int res[MXN]; int dist[MXN]; bool vis[MXN]; void bfs_dist(int source) { memset(vis, 0, sizeof vis); queue<pair<int, int> > proc; for (int i=0; i<N; i++) dist[i] = INT_MAX; proc.push(make_pair(source, 0)); // node, distance while (!proc.empty()) { int node = proc.front().first, dis = proc.front().second; proc.pop(); if (dist[node] < dis) { continue; } dist[node] = dis; int po = dis + 1; for (int i=0; i<adj[node].size(); i++) { int ot = adj[node][i]; if (dist[ot] > po) { dist[ot] = po; proc.push(make_pair(ot, po)); } } } } int limit = 0; int took = 0; vector<int> taken; bool blocked[MXN]; void travel(int node) { if (took >= limit) return; taken.push_back(node); took++; blocked[node] = true; for (int i=0; i<adj[node].size(); i++) { int ot = adj[node][i]; if (blocked[ot]) continue; travel(ot); } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { A = a; B = b; C = c; N = n; for (int i=0; i<n-1; i++) { adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]); } bfs_dist(0); int furthest = max_element(dist, dist+n) - dist; bfs_dist(furthest); int fmost = max_element(dist, dist+n) - dist; memset(blocked, 0, sizeof blocked); // cout << fmost << " for A" << endl; vector<int> re(n); re[fmost] = 1; blocked[fmost] = true; limit = b; took = 0; int sta = adj[fmost].front(); travel(sta); assert(taken.size() == b); for (int i=0; i<b; i++) { // cout << taken[i] << " for B" << endl; re[taken[i]] = 2; } for (int i=0; i<n; i++) { if (re[i] == 0) { // cout << i << " for C" << endl; re[i] = 3; } } return re; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2936 KB | ok, correct split |
2 | Correct | 4 ms | 2936 KB | ok, correct split |
3 | Correct | 4 ms | 2936 KB | ok, correct split |
4 | Incorrect | 5 ms | 2936 KB | invalid split: #1=1, #2=1, #3=2 |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2936 KB | ok, correct split |
2 | Correct | 4 ms | 2936 KB | ok, correct split |
3 | Runtime error | 8 ms | 5752 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 2808 KB | invalid split: #1=1, #2=1, #3=3 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 2808 KB | invalid split: #1=1, #2=2, #3=6 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2936 KB | ok, correct split |
2 | Correct | 4 ms | 2936 KB | ok, correct split |
3 | Correct | 4 ms | 2936 KB | ok, correct split |
4 | Incorrect | 5 ms | 2936 KB | invalid split: #1=1, #2=1, #3=2 |
5 | Halted | 0 ms | 0 KB | - |