Submission #204224

---

Source Code Expand

#include "animals.h"
#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

Compile Error

./grader.cpp: In function ‘int main()’:
./grader.cpp:15: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./grader.cpp:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./grader.cpp:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

Judge Result