Submission #505082

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
505082	2022-01-10T13:07:26 Z	tgbegimx	Dynamite (POI11_dyn)	C++17	90 / 100	1016 ms	23028 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;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	204 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	844 KB	Output is correct
2	Correct	21 ms	1392 KB	Output is correct
3	Correct	21 ms	1652 KB	Output is correct
4	Correct	27 ms	3368 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	2380 KB	Output is correct
2	Correct	68 ms	3116 KB	Output is correct
3	Correct	107 ms	3600 KB	Output is correct
4	Correct	78 ms	6468 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	88 ms	4292 KB	Output is correct
2	Correct	92 ms	4372 KB	Output is correct
3	Correct	119 ms	4388 KB	Output is correct
4	Correct	147 ms	9408 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	344 ms	8380 KB	Output is correct
2	Correct	412 ms	9468 KB	Output is correct
3	Correct	777 ms	17700 KB	Output is correct
4	Correct	788 ms	17576 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	990 ms	14584 KB	Output is correct
2	Correct	798 ms	12072 KB	Output is correct
3	Correct	961 ms	17348 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	972 ms	21008 KB	Output is correct
2	Correct	789 ms	12076 KB	Output is correct
3	Correct	1016 ms	23028 KB	Output is correct
4	Correct	158 ms	12080 KB	Output is correct

Submission #505082

Compilation message