Submission #210020

#	Time	Username	Problem	Language	Result	Execution time	Memory
210020		brcode	Race (IOI11_race)	C++14	100 / 100	1747 ms	57316 KiB

race

#include <iostream>
#include <race.h>
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 2e5+5;
long long ans =1e18;
long long sz[MAXN];
bool used[MAXN];
long long n,k;
map<long long,long long> m1;
vector<pair<long long,long long>> toadd;
long long currsz = 0;
vector<pair<long long,long long>> v1[MAXN];

void dfs(long long curr,long long par){
    currsz++;
    sz[curr] = 1;
    for(auto x:v1[curr]){
        if(!used[x.first] && x.first!=par){
            dfs(x.first,curr);
            sz[curr]+=sz[x.first];
        }
    }
}
long long centroid(long long curr,long long par){
    for(auto x:v1[curr]){
        if(!used[x.first] && x.first!=par && sz[x.first]>currsz/2){
            return centroid(x.first,curr);
        }
    }
    return curr;
}
void dfsans(long long curr,long long par,long long val,long long depth){
    for(auto x:v1[curr]){
        if(x.first!=par && !used[x.first]){
            toadd.push_back(make_pair(val+x.second,depth+1));
            dfsans(x.first,curr,val+x.second,depth+1);
        }
    }
}
void decompose(long long u,long long par){
    currsz = 0;
    dfs(u,u);
    long long cen = centroid(u,u);
    
    //link[cen] = par;
    //find all paths through the centroid
    m1.clear();
    for(auto x:v1[cen]){
        if(!used[x.first]){
            
            toadd.clear();
            toadd.push_back(make_pair(x.second,1));
            dfsans(x.first,cen,x.second,1);
            
        
            for(auto y:toadd){
    
                if(k-y.first>=0 && m1[k-y.first]){
                  //  cout<<x.first<<" "<<cen<<" "<<y.first<<endl;
                    ans = min(ans,m1[k-y.first]+y.second);
                }
                if(y.first == k){
                    
                    ans = min(ans,y.second);
                }
            }
            for(auto y:toadd){
               // cout<<cen<<" "<<y.first<<" "<<y.second<<endl;
               
                if(!m1[y.first]){
                    m1[y.first] = y.second;
                }else{
                    
                    m1[y.first] = min(m1[y.first],y.second);
                }
                
                
            }
        }
    }
    
    used[cen] = true;
    for(auto x:v1[cen]){
        if(!used[x.first]){
            decompose(x.first,cen);
        }
    }
    used[cen] = false;
}
int best_path(int N,int K,int H[][2],int L[]){
    n = N;
    k = K;
    for(long long i=0;i<n-1;i++){
        long long u = H[i][0];
        long long v = H[i][1];
        long long w = L[i];
        u++;v++;
        v1[u].push_back(make_pair(v,w));
        v1[v].push_back(make_pair(u,w));
    }
    decompose(1,1);
    if(ans == 1e18){
        return -1;
    }
    return (int)ans;
}
/*int main(){
    cin>>n>>k;
    for(long long i=0;i<n-1;i++){
        long long u,v,w;
        cin>>u>>v>>w;
        
        u++;v++;
        v1[u].push_back(make_pair(v,w));
        v1[v].push_back(make_pair(u,w));
    }
    decompose(1,1);
    cout<<ans<<endl;
}
*/

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