답안 #235324

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
235324 2020-05-27T22:38:28 Z giorgikob Dynamite (POI11_dyn) C++14
100 / 100
1669 ms 56000 KB
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 1e6 + 6;


bool is_dynamite[N];
int closest_explotion[N];
int furthest_dynamite[N];
int P[N],depth[N];
vector<int>gr[N];
int n,m;

void dfs(int x, int p){

        depth[x] = depth[p] + 1;
        P[x] = p;

        for(int to : gr[x]){
                if(to == p) continue;
                dfs(to,x);
        }
}

bool check(int k){
        //cout << k << endl;
        priority_queue<pair<int,int>>q;
        int cnt_dynamites = 0;

        for(int i = 1; i <= n; i++){
                q.push({depth[i],i});
                closest_explotion[i] = 1e9;
                furthest_dynamite[i] = is_dynamite[i] ? 0 : -1;
        }

        while(q.size()){
                auto pa = q.top();
                q.pop();
                int x = pa.second;
                int p = P[x];
                //cout << x << " " << furthest_dynamite[x] << " " << closest_explotion[x] << endl;
                if(furthest_dynamite[x] == k){
                        cnt_dynamites++;
                        if(cnt_dynamites > m) return false;
                        closest_explotion[p] = 1;
                } else {
                        if(closest_explotion[x] + furthest_dynamite[x] <= k && furthest_dynamite[x] != -1){
                                closest_explotion[p] = min(closest_explotion[p],closest_explotion[x]+1);
                                continue;
                        }
                        if(furthest_dynamite[x] != -1)furthest_dynamite[p] = max(furthest_dynamite[p],furthest_dynamite[x]+1);
                        closest_explotion[p] = min(closest_explotion[p],closest_explotion[x]+1);
                }
        }

        if(closest_explotion[1] + furthest_dynamite[1] > k && furthest_dynamite[1] != -1 && furthest_dynamite[1] != k){
                cnt_dynamites++;
                if(cnt_dynamites > m) return false;
        }

        return true;
}

int main(){

        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

        cin >> n >> m;
        for(int i = 1; i <= n; i++){
                cin >> is_dynamite[i];
        }

        for(int i = 1; i < n; i++){
                int x,y;
                cin >> x >> y;
                gr[x].pb(y);
                gr[y].pb(x);
        }

        dfs(1,0);

        int l = 0, r = n;
        int answer = -1;
        while(l <= r){
                int mid = l+r;
                mid >>= 1;
                if(check(mid)){
                        r = mid-1;
                        answer = mid;
                } else {
                        l = mid+1;
                }
        }

        cout << answer << endl;
}

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 19 ms 23808 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 23936 KB Output is correct
2 Correct 18 ms 23936 KB Output is correct
3 Correct 18 ms 23936 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 23936 KB Output is correct
2 Correct 19 ms 23936 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 23936 KB Output is correct
2 Correct 20 ms 23936 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 24632 KB Output is correct
2 Correct 78 ms 25816 KB Output is correct
3 Correct 97 ms 26140 KB Output is correct
4 Correct 101 ms 27324 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 27596 KB Output is correct
2 Correct 235 ms 30144 KB Output is correct
3 Correct 286 ms 30708 KB Output is correct
4 Correct 283 ms 32276 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 350 ms 30928 KB Output is correct
2 Correct 372 ms 32336 KB Output is correct
3 Correct 389 ms 31976 KB Output is correct
4 Correct 435 ms 35584 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 930 ms 37620 KB Output is correct
2 Correct 960 ms 43044 KB Output is correct
3 Correct 1224 ms 48344 KB Output is correct
4 Correct 1240 ms 48304 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1669 ms 46464 KB Output is correct
2 Correct 1366 ms 50256 KB Output is correct
3 Correct 1556 ms 52600 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1665 ms 50316 KB Output is correct
2 Correct 1340 ms 50380 KB Output is correct
3 Correct 1620 ms 56000 KB Output is correct
4 Correct 1042 ms 50696 KB Output is correct