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