Submission #2486613
Source Code Expand
#include "animals.h" #include<iostream> #include<vector> #include<algorithm> #include<map> #include<cassert> using namespace std; #define rep(i, n) for(int i = 0; i < (int)n; i++) #define each(i, c) for(__typeof(c.begin()) i = c.begin(); i != c.end(); i++) #define pb push_back #define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl; typedef vector<int> vi; const int MX = 100000; vector<vi> e; map<int, int> cnt; bool flag[MX]; int sz[MX], pa[MX]; void del(int c){ assert(cnt[c]); if(--cnt[c] == 0) cnt.erase(c); } int dfs(int c, int p){ sz[c] = 1; pa[c] = p; rep(i, e[c].size()) if(e[c][i] != p) sz[c] += dfs(e[c][i], c); return sz[c]; } void init(int N, int E[][2]) { e.resize(N); rep(i, N - 1){ int a = E[i][0], b = E[i][1]; e[a].pb(b); e[b].pb(a); } dfs(0, -1); cnt[sz[0]]++; } int query(int v) { int p = v; while(pa[p] >= 0 && !flag[pa[p]]) p = pa[p]; if(p != v){ del(sz[p]); for(p = v; pa[p] >= 0 && !flag[pa[p]]; p = pa[p]) sz[pa[p]] -= sz[v]; cnt[sz[p]]++; } else del(sz[v]); rep(i, e[v].size()) if(e[v][i] != pa[v]){ if(!flag[e[v][i]]) cnt[sz[e[v][i]]]++; } map<int, int>::iterator it = cnt.end(); it--; flag[v] = 1; sz[v] = 0; return it->first; }
Submission Info
Submission Time | |
---|---|
Task | A - むこのどうぶつたち と しんりんのはかい (Innocent Animals and Destruction of Forests) |
User | luogu_bot2 |
Language | C++ (GCC 5.4.1) |
Score | 0 |
Code Size | 1277 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 ...