| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 29337 |
2017-07-19T02:53:39 Z |
윤교준(#1168) |
Dynamite (POI11_dyn) |
C++11 |
|
3000 ms |
64240 KB |
#include <bits/stdc++.h>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[sz(V)-2])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define MAXN (300005)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }
struct BIT {
int d[MAXN];
void init() { fill(d, d+MAXN, 0); }
void upd(int x, int r) { for(; x < MAXN; x += rb(x)) d[x] += r; }
int get(int x) { int r = 0; for(; x; x -= rb(x)) r += d[x]; return r; }
int get(int s, int e) { return s > e ? 0 : get(e) - get(s-1); }
};
BIT bit;
vector<int> G[MAXN];
vector<pii> V; // {dep, idx}
int prt[MAXN][19], dep[MAXN], ord[MAXN], os[MAXN], oe[MAXN];
int A[MAXN], B[MAXN];
bool isb[MAXN];
int N, M;
int goup(int idx, int c) {
for(int i = 0; i < 19; i++) if(c & (1<<i)) idx = prt[idx][i];
return idx;
}
int lcad(int a, int b) {
int ret = 0;
if(dep[a] > dep[b]) swap(a, b);
int dt = dep[b] - dep[a];
for(int i = 0; i < 19; i++) if(dt & (1<<i)) { b = prt[b][i]; ret += (1<<i); }
if(a == b) return ret;
for(int i = 18; ~i; i--) if(prt[a][i] != prt[b][i]) {
a = prt[a][i]; b = prt[b][i]; ret += (1<<i)*2;
}
return ret + 2;
}
void dfs(int idx, int depth, int& c) {
dep[idx] = depth; c++; ord[idx] = os[idx] = oe[idx] = c;
for(int v : G[idx]) {
if(dep[v]) continue;
prt[v][0] = idx;
dfs(v, depth+1, c);
upmin(os[idx], os[v]);
upmax(oe[idx], oe[v]);
}
}
bool f(int T) {
bit.init();
vector<int> Q;
for(pii& v : V) {
int idx = v.second;
if(bit.get(idx)) continue;
bool flag = false;
for(int q : Q) {
int d = lcad(idx, q);
if(T < d) continue;
flag = true; break;
}
if(flag) continue;
int rt = goup(idx, T);
Q.pb(rt);
bit.upd(os[rt], 1);
bit.upd(oe[rt]+1, -1);
}
return sz(Q) <= M;
}
int getAns() {
int s = 0, e = N; for(int m; s < e;) {
m = (s+e)/2;
if(f(m)) e = m; else s = m+1;
}
return s;
}
int main() {
scanf("%d%d", &N, &M);
for(int i = 1, c; i <= N; i++) { scanf("%d", &c); isb[i] = c; }
for(int i = 1; i < N; i++) scanf("%d%d", &A[i], &B[i]);
for(int i = 1; i < N; i++) fg(G, A[i], B[i]);
{ int c = 0; dfs(1, 1, c); } prt[1][0] = 1;
//for(int i = 1; i <= N; i++) printf("%d : %d %d %d : %d %d\n", i, dep[i], prt[i][0], ord[i], os[i], oe[i]);
for(int j = 1; j < 19; j++) for(int i = 1; i <= N; i++) prt[i][j] = prt[prt[i][j-1]][j-1];
for(int i = 1; i <= N; i++) if(isb[i]) V.pb({dep[i], i});
sorv(V); revv(V);
printf("%d\n", getAns());
return 0;
}
Compilation message
dyn.cpp: In function 'int main()':
dyn.cpp:88:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
^
dyn.cpp:89:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1, c; i <= N; i++) { scanf("%d", &c); isb[i] = c; }
^
dyn.cpp:90:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i < N; i++) scanf("%d%d", &A[i], &B[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
39816 KB |
Output is correct |
| 2 |
Correct |
0 ms |
39816 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
39816 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
39816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
39816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
39816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
40212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
41824 KB |
Output is correct |
| 2 |
Correct |
86 ms |
43068 KB |
Output is correct |
| 3 |
Correct |
1313 ms |
43200 KB |
Output is correct |
| 4 |
Incorrect |
1253 ms |
46756 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
729 ms |
43636 KB |
Output is correct |
| 2 |
Correct |
153 ms |
44100 KB |
Output is correct |
| 3 |
Incorrect |
109 ms |
43168 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1018 ms |
49444 KB |
Output is correct |
| 2 |
Correct |
376 ms |
49320 KB |
Output is correct |
| 3 |
Execution timed out |
3000 ms |
58108 KB |
Execution timed out |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
929 ms |
53356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1186 ms |
64240 KB |
Output is correct |
| 2 |
Incorrect |
1496 ms |
53260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
