Submission #204214
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++] = nu;
}
}
++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
Set Name |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
20 / 20 |
0 / 25 |
0 / 55 |
Status |
|
|
|
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 |
25 ms |
992 KB |
subtask1/10 |
AC |
28 ms |
1148 KB |
subtask1/11 |
AC |
28 ms |
1176 KB |
subtask1/12 |
AC |
30 ms |
1100 KB |
subtask1/13 |
AC |
28 ms |
1016 KB |
subtask1/14 |
AC |
29 ms |
1172 KB |
subtask1/15 |
AC |
33 ms |
1140 KB |
subtask1/16 |
AC |
29 ms |
1176 KB |
subtask1/17 |
AC |
30 ms |
1216 KB |
subtask1/18 |
AC |
32 ms |
1148 KB |
subtask1/19 |
AC |
30 ms |
1148 KB |
subtask1/2 |
AC |
24 ms |
1016 KB |
subtask1/3 |
AC |
24 ms |
1144 KB |
subtask1/4 |
AC |
24 ms |
1052 KB |
subtask1/5 |
AC |
25 ms |
1012 KB |
subtask1/6 |
AC |
24 ms |
1008 KB |
subtask1/7 |
AC |
26 ms |
1012 KB |
subtask1/8 |
AC |
30 ms |
1152 KB |
subtask1/9 |
AC |
27 ms |
1188 KB |
subtask2/1 |
AC |
26 ms |
1044 KB |
subtask2/10 |
RE |
481 ms |
16272 KB |
subtask2/11 |
AC |
553 ms |
14224 KB |
subtask2/2 |
AC |
26 ms |
1052 KB |
subtask2/3 |
AC |
25 ms |
1124 KB |
subtask2/4 |
AC |
29 ms |
1048 KB |
subtask2/5 |
AC |
77 ms |
2576 KB |
subtask2/6 |
AC |
318 ms |
8728 KB |
subtask2/7 |
RE |
496 ms |
16396 KB |
subtask2/8 |
RE |
582 ms |
16408 KB |
subtask2/9 |
RE |
581 ms |
16524 KB |
subtask3/1 |
AC |
28 ms |
1048 KB |
subtask3/10 |
AC |
582 ms |
14228 KB |
subtask3/11 |
RE |
606 ms |
8696 KB |
subtask3/12 |
RE |
833 ms |
8700 KB |
subtask3/13 |
RE |
842 ms |
8708 KB |
subtask3/14 |
RE |
768 ms |
8728 KB |
subtask3/15 |
RE |
282 ms |
8476 KB |
subtask3/16 |
RE |
278 ms |
8464 KB |
subtask3/2 |
AC |
29 ms |
1228 KB |
subtask3/3 |
AC |
29 ms |
1044 KB |
subtask3/4 |
AC |
31 ms |
1160 KB |
subtask3/5 |
AC |
29 ms |
1192 KB |
subtask3/6 |
RE |
509 ms |
16416 KB |
subtask3/7 |
AC |
654 ms |
16020 KB |
subtask3/8 |
AC |
469 ms |
9100 KB |
subtask3/9 |
TLE |
2031 ms |
9092 KB |