| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 505080 |
2022-01-10T13:05:39 Z |
tgbegimx |
Dynamite (POI11_dyn) |
C++17 |
|
0 ms |
0 KB |
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <list>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f
#define PI 3.1415926535898
#define F first
#define S second
#define endl '\n'
#define lson rt << 1
#define rson rt << 1 | 1
#define f(x, y, z) for (int x = (y), __ = (z); x < __; ++x)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std;
const int maxn = 3e6 + 7;
int n, m;
int a[maxn], f1[maxn], f2[maxn], num;
struct pp
{
int v, w, next;
}edge[2 * maxn];
int head[maxn], cnt;
void add(int t1, int t2, int t3)
{
edge[++cnt].v = t2;
edge[cnt].w = t3;
edge[cnt].next = head[t1];
head[t1] = cnt;
}
void dfs(int u, int f, int k)
{
f1[u] = -inf, f2[u] = inf;
for (int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].v;
if (v == f) continue;
dfs(v, u, k);
f1[u] = max(f1[u], f1[v] + 1);
f2[u] = min(f2[u], f2[v] + 1);
}
IF (a [u] && f2 [u]> k) f1 [u] = max (0, f1 [u]); // cannot be subjected to the point of the subtree to hand over the parent node processing
IF (F1 [U] + F2 [U] <= K) F1 [U] = -inf; // Sub tree can be covered
IF (f1 [u] == k) // must be a coverage point
{
f1[u] = -inf, f2[u] = 0;
num++;
}
/ / Can't use else if
}
int check(int v)
{
num = 0;
dfs(1, -1, v);
IF (F1 [1]> = 0) Num ++; // Consider the case where the root node cannot be covered
return num <= m;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
_rep(i, 1, n) cin >> a[i];
int ta, tb;
_rep(i, 1, n - 1)
{
cin >> ta >> tb;
add(ta, tb, 1);
add(tb, ta, 1);
}
int l = 0, r = n;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
//IF (Check (L)) R = L; // Do not add this sentence will have a point
cout << r << endl;
}
Compilation message
dyn.cpp:60:17: warning: missing terminating ' character
60 | / / Can't use else if
| ^
dyn.cpp:60:17: error: missing terminating ' character
60 | / / Can't use else if
| ^~~~~~~~~~~~~~
dyn.cpp: In function 'void dfs(int, int, int)':
dyn.cpp:53:5: error: 'IF' was not declared in this scope; did you mean 'INF'?
53 | IF (a [u] && f2 [u]> k) f1 [u] = max (0, f1 [u]); // cannot be subjected to the point of the subtree to hand over the parent node processing
| ^~
| INF
dyn.cpp:54:14: error: 'F1' was not declared in this scope; did you mean 'f1'?
54 | IF (F1 [U] + F2 [U] <= K) F1 [U] = -inf; // Sub tree can be covered
| ^~
| f1
dyn.cpp:54:18: error: 'U' was not declared in this scope
54 | IF (F1 [U] + F2 [U] <= K) F1 [U] = -inf; // Sub tree can be covered
| ^
dyn.cpp:54:23: error: 'F2' was not declared in this scope; did you mean 'f2'?
54 | IF (F1 [U] + F2 [U] <= K) F1 [U] = -inf; // Sub tree can be covered
| ^~
| f2
dyn.cpp:54:33: error: 'K' was not declared in this scope
54 | IF (F1 [U] + F2 [U] <= K) F1 [U] = -inf; // Sub tree can be covered
| ^
dyn.cpp:60:10: error: expected primary-expression before '/' token
60 | / / Can't use else if
| ^
dyn.cpp:60:12: error: expected primary-expression before '/' token
60 | / / Can't use else if
| ^
dyn.cpp:60:14: error: 'Can' was not declared in this scope; did you mean 'tan'?
60 | / / Can't use else if
| ^~~
| tan
dyn.cpp: In function 'int check(int)':
dyn.cpp:66:14: error: 'F1' was not declared in this scope; did you mean 'f1'?
66 | IF (F1 [1]> = 0) Num ++; // Consider the case where the root node cannot be covered
| ^~
| f1
dyn.cpp:66:22: error: expected primary-expression before '=' token
66 | IF (F1 [1]> = 0) Num ++; // Consider the case where the root node cannot be covered
| ^
dyn.cpp:66:10: error: 'IF' was not declared in this scope; did you mean 'INF'?
66 | IF (F1 [1]> = 0) Num ++; // Consider the case where the root node cannot be covered
| ^~
| INF
