Submission #204216

---

Source Code Expand

#include "animals.h"
#include <algorithm>
#include <vector>
#include <queue>
#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));
}

int qv[MX], qvp[MX], qvs, qvt;
int qu[MX], qup[MX], qus, qut;
void calcSize(int v, int u) {
	int tot = m[v];
	qv[0] = v; qvp[0] = -1; qvs = 0; qvt = 1;
	qu[0] = u; qup[0] = -1; qus = 0; qut = 1;
	int cnt = 0;
	while (qvs < qvt && qus < qut) {
		{
			int nv = qv[qvs], np = qvp[qvs++];
			each(i, nv) {
				int nu = to[i];
				if (nu == np) continue;
				qv[qvt] = nu; qvp[qvt++] = nv;
			}
		}
		{
			int nv = qu[qus], np = qup[qus++];
			each(i, nv) {
				int nu = to[i];
				if (nu == np) continue;
				qu[qut] = nu; qup[qut++] = nv;
			}
		}
		++cnt;
	}
	if (qvs == qvt) {
		m[v] = cnt;
		m[u] = tot - cnt;
	} else {
		m[u] = cnt;
		m[v] = tot - 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