Submission #610906

#	Time	Username	Problem	Language	Result	Execution time	Memory
610906		PoonYaPat	Race (IOI11_race)	C++14	0 / 100	4 ms	5016 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]; //dis[x] : the least node count that have distance of x, also count root
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
    for (auto s : adj[x]) {
        if (mark[s.first] || s.first==par) continue;

        if (d+s.second<k) {
            now[d+s.second]=min({dis[d+s.second],cnt+1,now[d+s.second]});

            temp2.push_back(d+s.second); //change now
            temp.push_back(d+s.second); //change dis

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

            dfs(s.first,x,d+s.second,cnt+1);
        } else if (d+s.second==k) ans=min(ans,cnt+1);
    }
}

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;

        if (s.second<k) {
            now[s.second]=min({dis[s.second],2,now[s.second]});

            temp2.push_back(s.second); //change now
            temp.push_back(s.second); //change dis

            if (dis[k-s.second]!=INT_MAX) ans=min(ans,1+dis[k-s.second]);

            dfs(s.first,x,s.second,2);
        } else if (s.second==k) ans=min(ans,2);

        for (auto s : temp2) {
            dis[s]=now[s];
            now[s]=INT_MAX;
        }
        temp2.clear();
    }

    for (auto s : temp) dis[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-1;
}

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