Submission #235324

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
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;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	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

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	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

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	23936 KB	Output is correct
2	Correct	19 ms	23936 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	23936 KB	Output is correct
2	Correct	20 ms	23936 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	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

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	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

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	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

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	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

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	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

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	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

Submission #235324

Compilation message