Submission #204206


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

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 = 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

Submission Time
Task A - むこのどうぶつたち と しんりんのはかい (Innocent Animals and Destruction of Forests)
User snuke
Language IOI-Style C++ (GCC 5.4.1)
Score 0
Code Size 2168 Byte
Status WA
Exec Time 2052 ms
Memory 28320 KB

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

Set Name Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 20 0 / 25 0 / 55
Status
AC × 6
WA × 13
AC × 10
TLE × 1
AC × 4
WA × 3
TLE × 9
Set Name Test Cases
Subtask1 subtask1/1, subtask1/10, subtask1/11, subtask1/12, subtask1/13, subtask1/14, subtask1/15, subtask1/16, subtask1/17, subtask1/18, subtask1/19, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask1/8, subtask1/9
Subtask2 subtask2/1, subtask2/10, subtask2/11, subtask2/2, subtask2/3, subtask2/4, subtask2/5, subtask2/6, subtask2/7, subtask2/8, subtask2/9
Subtask3 subtask3/1, subtask3/10, subtask3/11, subtask3/12, subtask3/13, subtask3/14, subtask3/15, subtask3/16, subtask3/2, subtask3/3, subtask3/4, subtask3/5, subtask3/6, subtask3/7, subtask3/8, subtask3/9
Case Name Status Exec Time Memory
subtask1/1 AC 38 ms 8032 KB
subtask1/10 AC 42 ms 8216 KB
subtask1/11 AC 42 ms 8324 KB
subtask1/12 WA 52 ms 8216 KB
subtask1/13 WA 53 ms 8212 KB
subtask1/14 WA 47 ms 8224 KB
subtask1/15 WA 44 ms 8132 KB
subtask1/16 WA 44 ms 8212 KB
subtask1/17 WA 48 ms 8196 KB
subtask1/18 WA 42 ms 8216 KB
subtask1/19 AC 47 ms 8212 KB
subtask1/2 AC 37 ms 8140 KB
subtask1/3 WA 37 ms 8088 KB
subtask1/4 WA 36 ms 8092 KB
subtask1/5 WA 37 ms 8080 KB
subtask1/6 AC 36 ms 8128 KB
subtask1/7 WA 37 ms 8084 KB
subtask1/8 WA 38 ms 8080 KB
subtask1/9 WA 43 ms 8220 KB
subtask2/1 AC 41 ms 8080 KB
subtask2/10 AC 837 ms 28296 KB
subtask2/11 TLE 2033 ms 25752 KB
subtask2/2 AC 37 ms 8088 KB
subtask2/3 AC 38 ms 8132 KB
subtask2/4 AC 42 ms 8212 KB
subtask2/5 AC 96 ms 10132 KB
subtask2/6 AC 415 ms 18192 KB
subtask2/7 AC 809 ms 28308 KB
subtask2/8 AC 840 ms 28312 KB
subtask2/9 AC 852 ms 28316 KB
subtask3/1 AC 42 ms 8212 KB
subtask3/10 TLE 2035 ms 25732 KB
subtask3/11 TLE 2052 ms 21268 KB
subtask3/12 TLE 2035 ms 21324 KB
subtask3/13 TLE 2037 ms 21388 KB
subtask3/14 TLE 2034 ms 21268 KB
subtask3/15 TLE 2030 ms 21272 KB
subtask3/16 TLE 2030 ms 21332 KB
subtask3/2 WA 42 ms 8216 KB
subtask3/3 WA 43 ms 8208 KB
subtask3/4 WA 45 ms 8196 KB
subtask3/5 AC 48 ms 8316 KB
subtask3/6 AC 851 ms 28320 KB
subtask3/7 AC 850 ms 28312 KB
subtask3/8 TLE 2030 ms 22192 KB
subtask3/9 TLE 2034 ms 22272 KB