Submission #204210

---

Source Code Expand

#include "animals.h"
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#define rep(i,n) for(int i = 0; i < n; ++i)
#define each(i,n) for(set<int>::iterator i = n.begin(); i != n.end(); ++i)
#define fi first
#define se second
using namespace std;
typedef pair<int,int> P;

const int MX = 100005;

set<int> to[MX];
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(it, to[v]) {
		int u = *it;
		if(u == p) continue;
		dfs(u, v);
	}
	tv[v] = k;
}

void addEdge(int v, int u) {
	to[v].insert(u);
	to[u].insert(v);
}

void init(int N, int E[][2]) {
	rep(i,N-1) addEdge(E[i][0], E[i][1]);
	dfs(0);
	t = seg(N);
	m[0] = N;
	q.push(P(N, 0));
}

void calcSize(int v, int u) {
	int tot = m[v];
	queue<P> qv, qu;
	qv.push(P(v,-1));
	qu.push(P(u,-1));
	int cnt = 0;
	while (!qv.empty() && !qu.empty()) {
		//printf("%d %d\n",(int)qv.size(), (int)qu.size());
		//printf("front : %d %d\n",(int)qv.front().fi, (int)qu.front().fi);
		{
			int nv = qv.front().fi, np = qv.front().se; qv.pop();
			each(it, to[nv]) {
				int nu = *it;
				if (nu == np) continue;
				qv.push(P(nu, nv));
			}
		}
		{
			int nv = qu.front().fi, np = qu.front().se; qu.pop();
			each(it, to[nv]) {
				int nu = *it;
				if (nu == np) continue;
				qu.push(P(nu, nv));
			}
		}
		++cnt;
	}
	if (qv.empty()) {
		m[v] = cnt;
		m[u] = tot - cnt;
	} else {
		m[u] = cnt;
		m[v] = tot - cnt;
	}
}

void cut(int v, int u) {
	to[v].erase(u);
	to[u].erase(v);
	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 (!to[v].empty()) cut(v, *(to[v].begin()));
	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