Submission #782793

#	Time	Username	Problem	Language	Result	Execution time	Memory
782793		vjudge1	Race (IOI11_race)	C++17	100 / 100	486 ms	39420 KiB

race

#include<bits/stdc++.h>
#include "race.h"
using namespace std;
const int N = 2e5+37;
int mi = 1e7, n, k, p;
vector<array<int, 2>> adj[N];
vector<int> s(N), vis2(N), vis(N);
vector<int> best((int)1e6+37, 1e7); 
vector<array<int, 2>> mp;
vector<int> pff;

void dfs(int v, int p){
    int pf=0;
    s[v] = 1;
    vis[v] = 1;
    for(auto i: adj[v]){
        if(vis2[i[0]]||i[0]==p) continue;
        pf++;
        dfs(i[0], v); s[v]+=s[i[0]];
    }

}
int dfs2(int v, int p, int gh){

    for(auto i: adj[v]){
        if(vis2[i[0]]||i[0]==p) continue;
        if(s[i[0]]>=gh/2) return dfs2(i[0], v, gh);
    }
    return v;
}

void dfs3(int v,  int dist, int z, int p){
   // cout<<v<<" "<<dist<<" "<<z<<"\n";
    if(dist<=k){
	    mp.push_back({dist, z});
	    
	    for(auto i: adj[v]){

	        if(vis2[i[0]]||i[0]==p) continue;
	        dfs3(i[0], dist+i[1], z+1, v);
	    }
	}
}

void dfs4(int v){

    for(auto pf: adj[v]){
        if(vis2[pf[0]]) continue;   
        mp.clear();

        dfs3(pf[0], pf[1], 1, v);
       

        for(auto i: mp){
	        if(i[0]>k) continue;
	        if(best[k-i[0]]!=1e7){
	       		mi=min(mi, i[1]+best[k-i[0]]);
	        }
        }
        for(auto i: mp){
        	if(i[0]<=k){
	        	best[i[0]]=min(i[1], best[i[0]]);
	        	pff.push_back(i[0]);
        	}
        }
    }
}


void gh(int v){

    dfs(v, v); 

    int x = dfs2(v, v, s[v]);
    
    dfs4(x);

    for(auto i:pff) if(i<=k)best[i]=1e7;
    pff.clear();
	best[0]=0;
    vis2[x]=1, p++;
	
}

int best_path(int N, int K, int a[][2], int l[])
{	
	best[0]=0;
    n = N, k = K;

    for(int i= 0; i < n-1; i++){
        int x=a[i][0], y=a[i][1], z=l[i];
        adj[x].push_back({y, z});
        adj[y].push_back({x, z});
    }

    p=1;
    while(p){
        p=0;
        fill(vis.begin(), vis.end(), 0);
        for(int i = 0; i < n; i++)
            if(!vis2[i]&&!vis[i]) gh(i);
    }

    if(mi==1e7) return -1;
    return mi;
}

/*void f(){
	#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
}

signed main()
{
    f();
    int n, k; cin >> n >> k;
    int a[n-1][2], l[n-1];
    for(int i=0; i<n-1; i++){
        cin>>a[i][0]>>a[i][1] >> l[i];
    }

   cout<< best_path(n, k, a, l);

   cerr<<(float)clock()/CLOCKS_PER_SEC;
}*/

    

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