Submission #613601

#	Time	Username	Problem	Language	Result	Execution time	Memory
613601		PoonYaPat	Race (IOI11_race)	C++14	100 / 100	364 ms	36388 KiB

race

#include "race.h"

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int ans=INT_MAX,sz[200001],k;
int dis[1000001];
int now[1000001];
vector<pii> adj[200001];
vector<int> temp,temp2;
bool mark[200001];

int find_sz(int x, int par) {
    sz[x]=1;
    for (auto s : adj[x]) {
        if (s.first==par || mark[s.first]) continue;
        sz[x]+=find_sz(s.first,x);
    }
    return sz[x];
}

int cen(int x, int par, int n) {
    for (auto s : adj[x]) {
        if (s.first!=par && !mark[s.first] && sz[s.first]>n/2) return cen(s.first,x,n);
    }
    return x;
}

void dfs(int x, int par, int d, int cnt) { // d=distance, consider node x
    if (d<k) {
        now[d]=min({now[d],cnt,dis[d]});

        temp2.push_back(d);
        temp.push_back(d);

        if (dis[k-d]!=INT_MAX) ans=min(ans,cnt+dis[k-d]);

        for (auto s : adj[x]) if (!mark[s.first] && s.first!=par) dfs(s.first,x,d+s.second,cnt+1);
    } else if (d==k) ans=min(ans,cnt);
}

void sol(int x) {
    int centroid=cen(x,x,find_sz(x,x));
    mark[centroid]=true;

    for (auto s : adj[centroid]) {
        if (mark[s.first]) continue;
        dfs(s.first,centroid,s.second,1);
        for (auto s : temp2) dis[s]=now[s];
        temp2.clear();
    }

    for (auto s : temp) dis[s]=INT_MAX,now[s]=INT_MAX;
    temp.clear();

    for (auto s : adj[centroid]) if (!mark[s.first]) sol(s.first);
}

int best_path(int n, int K, int H[][2], int L[]) {
    k=K;
    for (int i=1; i<=K; ++i) dis[i]=INT_MAX,now[i]=INT_MAX;
    for (int i=0; i<n-1; ++i) {
        adj[H[i][0]].push_back(pii(H[i][1],L[i]));
        adj[H[i][1]].push_back(pii(H[i][0],L[i]));
    }
    sol(1);
    if (ans==INT_MAX) return -1;
    return ans;
}

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