Submission #210014

#	Time	Username	Problem	Language	Result	Execution time	Memory
210014		brcode	Race (IOI11_race)	C++14	0 / 100	8 ms	5112 KiB

race

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

void dfs(int curr,int 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];
        }
    }
}
int centroid(int curr,int 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(int curr,int par,int val,int 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(int u,int par){
    currsz = 0;
    dfs(u,u);
    int cen = centroid(u,u);
    //cout<<cen<<endl;
    //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(cen == 1){
             //   cout<<x.first<<" "<<y.first<<" "<<123<<endl;
            }
            if(k-y.first>=0 && m1[k-y.first]){
              //  cout<<cen<<" "<<m1[k-y.first]+y.second<<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(int i=0;i<n-1;i++){
        int u = H[i][0];
        int v = H[i][1];
        int 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 == 1e9){
        return -1;
    }
    return ans;
}

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