Submission #1030147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030147		kl0989e	Race (IOI11_race)	C++17	100 / 100	639 ms	55380 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

const int maxn=2e5+10;
vector<vector<pi>> graph(maxn);
vi sze(maxn);
vi cen_num(maxn,-1);
int ans=1e9;
int needed;
map<int,int> added;
map<int,int> now;

void dfs2(int cur, int prev, int len, int dist) {
    if (now.find(len)==now.end() || now[len]>dist) {
        if (len==needed) {
            ans=min(ans,dist);
        }
        else {
            now[len]=dist;
        }
    }
    for (auto [to,w]:graph[cur]) {
        if (to==prev || len+w>needed || cen_num[to]!=-1) {
            continue;
        }
        dfs2(to,cur,len+w,dist+1);
    }
}

void dfs(int cur, int prev, int num, int cur_sze) {
    sze[cur]=1;
    bool is_cen=1;
    for (auto [to,_]:graph[cur]) {
        if (to==prev || cen_num[to]!=-1) {
            continue;
        }
        dfs(to,cur,num,cur_sze);
        if (cen_num[cur]!=-1) {
            return;
        }
        sze[cur]+=sze[to];
        if (sze[to]>cur_sze/2) {
            is_cen=0;
        }
    }
    if (!is_cen || cur_sze-sze[cur]>cur_sze/2) {
        return;
    }
    cen_num[cur]=num;
    for (auto [to,w]:graph[cur]) {
        if (cen_num[to]!=-1 || w>needed) {
            continue;
        }
        dfs2(to,cur,w,1);
        if (now.size()>added.size()) {
            swap(now,added);
        }
        for (auto [a,b]:now) {
            if (added.find(needed-a)!=added.end() && added[needed-a]+b<ans) {
                ans=added[needed-a]+b;
            }
        }
        for (auto [a,b]:now) {
            if (added.find(a)==added.end() || added[a]>b) {
                added[a]=b;
            }
        }
        now.clear();
    }
    added.clear();
    for (auto [to,_]:graph[cur]) {
        if (cen_num[to]!=-1) {
            continue;
        }
        if (prev==to) {
            dfs(to,cur,num+1,cur_sze-sze[cur]);
        }
        else {
            dfs(to,cur,num+1,sze[to]);
        }
    }
}

int best_path(int n, int k, int edge[][2], int len[]) {
    for (int i=0; i<n-1; i++) {
        graph[edge[i][0]].pb({edge[i][1],len[i]});
        graph[edge[i][1]].pb({edge[i][0],len[i]});
    }
    needed=k;
    dfs(0,-1,0,n);
    return (ans==1e9?-1:ans);
}

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