oj.uz

답안 #505082

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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