Submission #235324

#	Time	Username	Problem	Language	Result	Execution time	Memory
235324		giorgikob	Untitled (POI11_dyn)	C++14	100 / 100	1669 ms	56000 KiB

Main

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10