Submission #204208

---

Source Code Expand

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

const int MX = 100005;

vector<int> to[MX], re[MX], used[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++;
	rep(i,to[v].size()) {
		int u = to[v][i];
		if(u == p) continue;
		dfs(u, v);
	}
	tv[v] = k;
}

void addEdge(int v, int u) {
	to[v].push_back(u);
	re[v].push_back((int)to[u].size());
	used[v].push_back(0);

	to[u].push_back(v);
	re[u].push_back((int)to[v].size() - 1);
	used[u].push_back(0);
}

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));
}

int lim, cnt;
void cfs(int v, int p=-1) {
	if (!lim) { cnt = -1; return;}
	--lim; ++cnt;
	for (int i = 0; i < to[v].size(); ++i) {
		int u = to[v][i];
		if (u == p || used[v][i]) continue;
		cfs(u, v);
		if (!lim) return;
	}
}

void cut(int v, int ei) {
	if (used[v][ei]) return;
	int u = to[v][ei];
	used[v][ei] = used[u][re[v][ei]] = 1;
	if (sv[v] > sv[u]) swap(v,u);
	int vx = kv[t.get(sv[v])];
	int mv = m[vx];
	lim = mv/2; cnt = 0; cfs(v); m[vx] = cnt;
	lim = mv/2; cnt = 0; cfs(u); m[u] = cnt;
	if (m[vx] == -1) m[vx] = mv - m[u];
	else m[u] = mv - m[vx];
	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) {
	rep(i, to[v].size()) cut(v, i);
	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