Submission #944584

#	Time	Username	Problem	Language	Result	Execution time	Memory
944584		irmuun	Race (IOI11_race)	C++17	100 / 100	1765 ms	77392 KiB

race

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pb push_bacK
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
 
const ll maxn=2e5+5;
 
int n=0;
set<pair<int,int> >adj[maxn];
vector<ll>sz(maxn),d(maxn);
 
void calc(int x,int p){
    n++;
    sz[x]=1;
    for(auto [y,w]:adj[x]){
        if(y!=p){
            calc(y,x);
            sz[x]+=sz[y];
        }
    }
}
 
int centroid(int x,int p){
    for(auto [y,w]:adj[x]){
        if(y==p) continue;
        if(sz[y]*2>n) return centroid(y,x);
    }
    return x;
}
 
void calc_dist(int x,int p){
    for(auto [y,w]:adj[x]){
        if(y!=p){
            d[y]=d[x]+w;
            calc_dist(y,x);
        }
    }
}
 
int best_path(int N,int K,int H[][2],int L[]){
    for(int i=0;i<N-2;i++){
        adj[H[i][0]].insert({H[i][1],L[i]});
        adj[H[i][1]].insert({H[i][0],L[i]});
    }
    int ans=1e9;
    queue<int>q;
    q.push(0);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        n=0;
        calc(x,-1);
        int root=centroid(x,-1);
        map<ll,int>dist;
        map<ll,int>cur,clr;
        vector<pair<int,int>>v;
        function <void(int,int,int)> dfs=[&](int x,int p,int depth){
            if(cur[d[x]]==0){
                cur[d[x]]=depth;
            }
            else{
                cur[d[x]]=min(cur[d[x]],depth);
            }
            for(auto [y,w]:adj[x]){
                if(y!=p){
                    d[y]=d[x]+w;
                    dfs(y,x,depth+1);
                }
            }
        };
        for(auto [y,w]:adj[root]){
            cur=clr;
            d[y]=w;
            dfs(y,root,1);
            for(auto [i,val]:cur){
                if(i==K){
                    if(val>0){
                        ans=min(ans,val);
                    }
                }
                else if(i<K){
                    if(val>0&&dist[K-i]>0){
                        ans=min(ans,val+dist[K-i]);
                    }
                }
            }
            for(auto [i,val]:cur){
                if(dist[i]==0){
                    dist[i]=val;
                }
                else if(val>0){
                    dist[i]=min(dist[i],val);
                }
            }
        }
        for(auto [y,w]:adj[root]){
            adj[y].erase({root,w});
            q.push(y);
        }
        adj[root].clear();
    }
    if(ans==1e9) ans=-1;
    return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57