Submission #505082

#	Time	Username	Problem	Language	Result	Execution time	Memory
505082		tgbegimx	Untitled (POI11_dyn)	C++17	90 / 100	1016 ms	23028 KiB

Main

#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
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10