Submission #204211
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));
}
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()) {
{
int nv = qv.front().fi, np = qv.front().se; qv.pop();
each(i, nv) {
int nu = to[i];
if (nu == np) continue;
qv.push(P(nu, nv));
}
}
{
int nv = qu.front().fi, np = qu.front().se; qu.pop();
each(i, nv) {
int nu = to[i];
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) {
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];
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 |
0 / 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 |
506 ms |
1420 KB |
subtask1/10 |
WA |
41 ms |
1524 KB |
subtask1/11 |
WA |
39 ms |
1432 KB |
subtask1/12 |
AC |
38 ms |
1428 KB |
subtask1/13 |
AC |
41 ms |
1516 KB |
subtask1/14 |
WA |
39 ms |
1440 KB |
subtask1/15 |
WA |
41 ms |
1512 KB |
subtask1/16 |
WA |
38 ms |
1428 KB |
subtask1/17 |
WA |
39 ms |
1436 KB |
subtask1/18 |
WA |
41 ms |
1428 KB |
subtask1/19 |
AC |
38 ms |
1416 KB |
subtask1/2 |
AC |
31 ms |
1380 KB |
subtask1/3 |
AC |
34 ms |
1392 KB |
subtask1/4 |
AC |
33 ms |
1416 KB |
subtask1/5 |
AC |
33 ms |
1420 KB |
subtask1/6 |
WA |
33 ms |
1416 KB |
subtask1/7 |
WA |
33 ms |
1420 KB |
subtask1/8 |
AC |
33 ms |
1416 KB |
subtask1/9 |
WA |
38 ms |
1420 KB |
subtask2/1 |
AC |
34 ms |
1420 KB |
subtask2/10 |
WA |
1023 ms |
16528 KB |
subtask2/11 |
AC |
722 ms |
14484 KB |
subtask2/2 |
WA |
34 ms |
1412 KB |
subtask2/3 |
WA |
33 ms |
1420 KB |
subtask2/4 |
WA |
40 ms |
1432 KB |
subtask2/5 |
WA |
113 ms |
2844 KB |
subtask2/6 |
WA |
464 ms |
9012 KB |
subtask2/7 |
WA |
973 ms |
16532 KB |
subtask2/8 |
WA |
911 ms |
16540 KB |
subtask2/9 |
WA |
946 ms |
16528 KB |
subtask3/1 |
WA |
42 ms |
1512 KB |
subtask3/10 |
AC |
749 ms |
14480 KB |
subtask3/11 |
TLE |
2039 ms |
7952 KB |
subtask3/12 |
TLE |
2040 ms |
7968 KB |
subtask3/13 |
TLE |
2044 ms |
7968 KB |
subtask3/14 |
TLE |
2046 ms |
7960 KB |
subtask3/15 |
TLE |
2048 ms |
7960 KB |
subtask3/16 |
TLE |
2043 ms |
7960 KB |
subtask3/2 |
WA |
43 ms |
1432 KB |
subtask3/3 |
WA |
43 ms |
1436 KB |
subtask3/4 |
AC |
46 ms |
1436 KB |
subtask3/5 |
AC |
39 ms |
1424 KB |
subtask3/6 |
WA |
916 ms |
16560 KB |
subtask3/7 |
WA |
899 ms |
16660 KB |
subtask3/8 |
TLE |
2043 ms |
9084 KB |
subtask3/9 |
TLE |
2050 ms |
8716 KB |