Submission #60114

#	Time	Username	Problem	Language	Result	Execution time	Memory
60114		naderjemel	Race (IOI11_race)	C++14	100 / 100	1136 ms	98020 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define MAX_N 200000
#define MAX_K 1000000
vector<vector<pair<int,int> >  > adj;
int n,k,nn;
bool pross[MAX_N];
int sub[MAX_N],cnt;
int dist[MAX_K],book[MAX_K],bk,rs;
int dfs(int u, int p){nn++;
    sub[u]=0;
    for(pair<int,int> i:adj[u]){
        if(!pross[i.first] && i.first!=p){
            dfs(i.first,u);
            sub[u]+=1+sub[i.first];
        }
    }
    return sub[u];
}
int find(int u, int p){
    for(pair<int,int> i:adj[u]){
        if(!pross[i.fi] && i.fi!=p && sub[i.fi]>nn/2){
            return find(i.fi,u);
        }
    }
    return u;
}
void check(int u, int p, int ed, int d){
    if(d>k) return;
    if(book[k-d]==bk && dist[k-d]+ed<rs) rs=dist[k-d]+ed;
    if(d==k && ed<rs) rs=ed;
    for(pair<int,int> i:adj[u]){
        if(!pross[i.fi] && i.fi!=p){
            check(i.fi,u,ed+1,d+i.se);
        }
    }
}
void fill(int u, int p, int ed, int d){
    if(d>k) return;
    if(book[d]<bk){
        book[d]=bk;
        dist[d]=ed;
    }
    else dist[d]=min(ed,dist[d]);
    for(pair<int,int> i:adj[u]){
        if(!pross[i.fi] && i.fi!=p){
            fill(i.fi,u,ed+1,d+i.se);
        }
    }
}
void solve(int u){nn=0;
    dfs(u,-1);
    if(sub[u]<=1) return;
    int cnt=find(u,-1);
    bk++;
    for(pair<int,int> i:adj[cnt]){
        if(!pross[i.fi]){   
            check(i.fi,cnt,1,i.se);
            fill(i.fi,cnt,1,i.se);
        }
    }
    pross[cnt]=true;
    for(pair<int,int> i:adj[cnt]){   
        if(!pross[i.fi]){   
            solve(i.fi);
        }
    }
}
int best_path(int N, int K, int H[][2], int L[]){n=N; k=K;
    adj.resize(N+2,vector<pair<int,int> >());
    for(int i=0;i<N-1;i++){
        adj[H[i][0]].push_back(make_pair(H[i][1],L[i]));
        adj[H[i][1]].push_back(make_pair(H[i][0],L[i]));
    }rs=1e9;
    solve(0);
    if(rs==1e9) return -1;
    else return rs;
}

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