Submission #2329140
Source Code Expand
#include <algorithm> #include <vector> #include <queue> #include <stack> #define rep(i,n) for(int i = 0; i < n; ++i) #define each(i,v) for(int i = head[v]; i != -1; i = next[i]) #define fi first #define se second using namespace std; typedef pair<int,int> P; const int MX = 100005; int to[MX*2], head[MX], next[MX*2], prev[MX*2], g; int sv[MX], tv[MX], k, kv[MX]; int m[MX]; priority_queue<P> q; struct seg { vector<int> d; int sz; seg() {} seg(int mx) { sz = 1; while (sz <= mx) sz <<= 1; d.resize(sz << 1, 0); } void add(int a, int b, int x, int i=1, int l=0, int r=-1) { if (r == -1) r = sz; if (a <= l && r <= b) { d[i] = max(d[i], x); return; } int c = l+r>>1; if (a < c) add(a, b, x, i<<1, l, c); if (c < b) add(a, b, x, i<<1|1, c, r); } int get(int i) { i += sz; int res = -1; while (i) { res = max(res, d[i]); i >>= 1; } return res; } } t; void dfs(int v, int p = -1){ kv[k] = v; sv[v] = k++; each(i, v) { int u = to[i]; if(u == p) continue; dfs(u, v); } tv[v] = k; } void addEdge(int v, int u) { to[g] = u; next[g] = head[v]; prev[g] = -1; if (head[v] != -1) prev[head[v]] = g; head[v] = g++; to[g] = v; next[g] = head[u]; prev[g] = -1; if (head[u] != -1) prev[head[u]] = g; head[u] = g++; } void init(int N, int E[][2]) { rep(i,N) head[i] = -1; rep(i,N-1) addEdge(E[i][0], E[i][1]); dfs(0); t = seg(N); m[0] = N; q.push(P(N, 0)); } struct dat { int v, p, i; dat() {} dat(int v, int p, int i): v(v), p(p), i(i) {} }; bool proc(stack<dat>& st) { dat d; while (1) { d = st.top(); st.pop(); if (d.i != -1 && to[d.i] == d.p) d.i = next[d.i]; if (d.i != -1) break; if (st.empty()) return true; } int i = d.i; d.i = next[d.i]; st.push(d); st.push(dat(to[i], d.v, head[to[i]])); return false; } void calcSize(int v, int u) { int tot = m[v]; int cnt = 1; stack<dat> stv, stu; stv.push(dat(v, -1, head[v])); stu.push(dat(u, -1, head[u])); while (1) { if (proc(stv) || proc(stu)) break; ++cnt; } if (!stv.empty()) m[v] = tot - cnt, m[u] = cnt; else m[u] = tot - cnt, m[v] = cnt; } void cut(int v, int u) { if (sv[v] > sv[u]) swap(v,u); int vx = kv[t.get(sv[v])]; calcSize(vx, u); q.push(P(m[vx], vx)); q.push(P(m[u], u)); t.add(sv[u], tv[u], sv[u]); while (1) { P p = q.top(); if (m[p.se] == p.fi) break; q.pop(); } } int query(int v) { while(head[v] != -1) { int i = head[v]; int u = to[i]; int re = i^1; if (prev[re] != -1) next[prev[re]] = next[re]; else head[u] = next[re]; if (next[re] != -1) prev[next[re]] = prev[re]; head[v] = next[i]; cut(v, u); } return q.top().fi; }
Submission Info
Submission Time | |
---|---|
Task | A - むこのどうぶつたち と しんりんのはかい (Innocent Animals and Destruction of Forests) |
User | I_love_you_Susan |
Language | C++ (GCC 5.4.1) |
Score | 0 |
Code Size | 2767 Byte |
Status | CE |
Compile Error
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 0 has invalid symbol index 11 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 1 has invalid symbol index 12 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 2 has invalid symbol index 2 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 3 has invalid symbol index 2 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 4 has invalid symbol index 11 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 5 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 6 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 7 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 8 has invalid symbol ...