# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
25444 | 2017-06-22T07:37:28 Z | 김현수(#1065) | Synchronization (JOI13_synchronization) | C++11 | 166 ms | 31112 KB |
#include<bits/stdc++.h> #define X first #define Y second using namespace std; typedef long long ll; typedef pair<ll,ll> pll; ll n, m, q, a[200005], par[200005]; ll pos[200005], chk[200005], ans; pll e[200005]; vector<ll> adj[200005]; vector<pll> gg[200005]; void calc (ll C, ll P) { par[C] = P; for(auto &T : adj[C]) { if(T == P) continue; calc(T, C); } } void solve (ll C, ll P) { if(P) { for(auto &T : gg[C]) { if(T.X <= pos[P]) { pos[C] = min(pos[P], T.Y); break; } } } if(pos[C]) ans++; for(auto &T : adj[C]) { if(T == P) continue; solve(T, C); } } void solve1() { ll R; scanf("%lld",&R); for(ll i=1;i<n;i++) { adj[e[i].X].push_back(e[i].Y); adj[e[i].Y].push_back(e[i].X); } calc(R, 0); for(ll i=1;i<n;i++) { if(par[e[i].X] != e[i].Y) swap(e[i].X, e[i].Y); } for(ll i=1;i<=m;i++) { if(chk[a[i]]) { gg[e[a[i]].X].push_back({chk[a[i]], i-1}); chk[a[i]] = 0; } else chk[a[i]] = i; } for(ll i=1;i<n;i++) { if(chk[i]) gg[e[i].X].push_back({chk[i], m}); reverse(gg[e[i].X].begin(), gg[e[i].X].end()); } pos[R] = m; solve(R, 0); printf("%lld\n",ans); } void solve2() {} int main() { scanf("%lld%lld%lld",&n,&m,&q); for(ll i=1;i<n;i++) { scanf("%lld%lld",&e[i].X,&e[i].Y); } for(ll i=1;i<=m;i++) scanf("%lld",&a[i]); q == 1 ? solve1() : solve2(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 20768 KB | Output is correct |
2 | Correct | 6 ms | 20768 KB | Output is correct |
3 | Correct | 0 ms | 20768 KB | Output is correct |
4 | Correct | 3 ms | 20768 KB | Output is correct |
5 | Correct | 6 ms | 20768 KB | Output is correct |
6 | Correct | 0 ms | 20900 KB | Output is correct |
7 | Correct | 16 ms | 21560 KB | Output is correct |
8 | Correct | 13 ms | 21428 KB | Output is correct |
9 | Correct | 16 ms | 21560 KB | Output is correct |
10 | Correct | 166 ms | 27896 KB | Output is correct |
11 | Correct | 166 ms | 27896 KB | Output is correct |
12 | Correct | 93 ms | 29812 KB | Output is correct |
13 | Correct | 83 ms | 28300 KB | Output is correct |
14 | Correct | 119 ms | 27632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 116 ms | 30776 KB | Output is correct |
2 | Correct | 89 ms | 29664 KB | Output is correct |
3 | Correct | 66 ms | 31112 KB | Output is correct |
4 | Correct | 63 ms | 30500 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 20768 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 63 ms | 20768 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 20768 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |