Submission #1287953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287953		soumil69	Race (IOI11_race)	C++17	43 / 100	235 ms	86544 KiB

race

#include <bits/stdc++.h>

using namespace std;
// #define int long long
#define ll long long

const int MX = 2e5+1;

map<ll,int> col[MX];
vector<pair<int,ll>> adj[MX];
ll ans = 1e9, k, n;
ll w[MX], dep[MX];

void init(int cur,int par,ll dis,ll dp){
    w[cur] = dis;
    dep[cur] = dp++;
    for(pair<int,ll>& nxt:adj[cur]){
        if(nxt.first != par){
            init(nxt.first,cur,dis+nxt.second,dp);
        }
    }
}

void dfs(int cur,int par){
    if(w[cur] == k){
        ans = min(ans,dep[cur]);
    }
    col[cur][w[cur]] = dep[cur];
    for(pair<int,ll>& nxt:adj[cur]){
        int nx = nxt.first;
        if(nx == par) continue;
        dfs(nx,cur);

        if(col[cur].size() < col[nx].size()){
            swap(col[cur],col[nx]);
        }
        ll req = k + 2*w[cur];
        for(auto cols:col[nx]){
            ll rem = req - cols.first;
            if(col[cur].count(rem)){
                ans = min(ans,cols.second+col[cur][rem] - 2ll*dep[cur]);
            }
            if(!col[cur].count(cols.first) || col[cur][cols.first] > cols.second){
                col[cur][cols.first] = cols.second;
            }
        }
    }
}

int best_path(int N, int K, int edges[][2], int weights[]) {
	n = N;
    k = K;
	ans = 1e9;
	for (int i = 0; i < n - 1; i++) {
		int u = edges[i][0];
		int v = edges[i][1];
        u++,v++;
		adj[u].push_back({v, weights[i]});
		adj[v].push_back({u, weights[i]});
	}
	init(1,0,0,0);
	dfs(1,0);
	return ans > N ? -1 : ans;
}

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