Submission #797935

#	Time	Username	Problem	Language	Result	Execution time	Memory
797935		Khizri	Race (IOI11_race)	C++17	9 / 100	3052 ms	10460 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5;
int n,k,par[mxn],sub[mxn],color[mxn],sz,first,ans=1e9;
map<int,int>global,local;
vector<pii>vt[mxn];
void calc(int u,int p){
    sz++;
    sub[u]=1;
    for(pii pp:vt[u]){
        int v=pp.F;
        if(v!=p&&!color[v]){            
            calc(v,u);
            sub[u]+=sub[v];
        }
    }
}
int find_centroid(int u,int p){
    for(pii pp:vt[u]){
        int v=pp.F;
        if(v==p) continue;
        if(sub[v]*2>sz){
            return find_centroid(v,u);
        }
    }
    return u;
}
void dfs(int u,int p,ll dis,int dep){
    if(dis==k) ans=min(ans,dep);
    if(dep>0&&dis<=k){
        if(global[k-dis]!=0){
            ans=min(ans,dep+global[k-dis]);
        }
        if(local[dis]==0){
            local[dis]=dep;
        }
        else{
            local[dis]=min(local[dis],dep);
        }
    }
    for(pii pp:vt[u]){
        int v=pp.F,len=pp.S;
        if(dep==0) local.clear();
        if(v!=p){
            dfs(v,u,dis+len,dep+1);
            if(dep==0){
                for(auto it=local.begin();it!=local.end();it++){
                    int x=it->F;
                    int y=it->S;
                    if(global[x]==0){
                        global[x]=y;
                    }
                    else{
                        global[x]=min(global[x],y);
                    }
                }
            }
        }
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    n=N,k=K;
    for(int i=0;i<n-1;i++){
        int u=H[i][0]+1,v=H[i][1]+1;
        vt[u].pb({v,L[i]});
        vt[v].pb({u,L[i]});
        if(L[i]==k) return 1;
    }
    for(int id=1;id<=20;id++){
        for(int i=1;i<=n;i++){
            if(!color[i]){
                sz=0;
                calc(i,-1);
                int node=find_centroid(i,-1);
                color[node]=1;
                global.clear();
                local.clear();
                dfs(node,-1,0,0);
            }
        }
    }
    if(ans==1e9) return -1;
    return ans;
}

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