Submission #235325

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
235325	2020-05-27T22:42:58 Z	giorgikob	Dynamite (POI11_dyn)	C++14	100 / 100	1826 ms	51480 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_explosion[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_explosion[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_explosion[x] << endl;
                if(furthest_dynamite[x] == k){
                        cnt_dynamites++;
                        if(cnt_dynamites > m) return false;
                        closest_explosion[p] = 1;
                } else {
                        closest_explosion[p] = min(closest_explosion[p],closest_explosion[x]+1);
                        if(closest_explosion[x] + furthest_dynamite[x] <= k && furthest_dynamite[x] != -1){
                                continue;
                        }
                        if(furthest_dynamite[x] != -1)furthest_dynamite[p] = max(furthest_dynamite[p],furthest_dynamite[x]+1);
                }
        }

        if(closest_explosion[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	20 ms	23808 KB	Output is correct
2	Correct	19 ms	23808 KB	Output is correct
3	Correct	18 ms	23936 KB	Output is correct
4	Correct	20 ms	23808 KB	Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	23936 KB	Output is correct
2	Correct	20 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	40 ms	24720 KB	Output is correct
2	Correct	83 ms	25488 KB	Output is correct
3	Correct	107 ms	25916 KB	Output is correct
4	Correct	97 ms	26916 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	179 ms	27496 KB	Output is correct
2	Correct	236 ms	29092 KB	Output is correct
3	Correct	281 ms	29468 KB	Output is correct
4	Correct	302 ms	31116 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	361 ms	30888 KB	Output is correct
2	Correct	390 ms	30960 KB	Output is correct
3	Correct	389 ms	30572 KB	Output is correct
4	Correct	442 ms	33940 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	998 ms	37656 KB	Output is correct
2	Correct	974 ms	39524 KB	Output is correct
3	Correct	1351 ms	44540 KB	Output is correct
4	Correct	1323 ms	44620 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1826 ms	46560 KB	Output is correct
2	Correct	1363 ms	45780 KB	Output is correct
3	Correct	1571 ms	48232 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1606 ms	50324 KB	Output is correct
2	Correct	1346 ms	45700 KB	Output is correct
3	Correct	1628 ms	51480 KB	Output is correct
4	Correct	1070 ms	46040 KB	Output is correct

Submission #235325

Compilation message