oj.uz

Submission #235323

# Submission time Handle Problem Language Result Execution time Memory
235323 2020-05-27T22:21:06 Z giorgikob Dynamite (POI11_dyn) C++14
20 / 100
 1644 ms 50300 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){

        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];
                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);
                }
        }
}

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;
}

Compilation message

dyn.cpp: In function 'bool check(int)':
dyn.cpp:58:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 23936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 23936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
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 #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 24672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 155 ms 27496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 355 ms 30808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 892 ms 37564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1644 ms 46664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1543 ms 50300 KB Output isn't correct
2 Halted 0 ms 0 KB -