Submission #1207976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207976		segfault_ikuyo	Race (IOI11_race)	C++20	100 / 100	266 ms	48452 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back

const int maxn=2e5+5;
const int maxk=1e6+5;

vector<pii> adj[maxn];
pii path[maxk];
int vis[maxn],siz[maxn];
int n,k,a,b,c;
int ans;
queue<pii> q;

int dfssiz(int x,int p){
    int sizz=1;
    for(pii i:adj[x]){
        if(i.f==p||vis[i.f]) continue;
        sizz+=dfssiz(i.f,x);
    }
    siz[x]=sizz;
    return sizz;
}

int dfsget(int x,int p,int c){
    for(pii i:adj[x]){
        if(i.f==p||vis[i.f]) continue;
        if(siz[i.f]>=siz[c]>>1) return dfsget(i.f,x,c);
    }
    return x;
}

void dfssolve(int x,int p,int d,int dd,int c){
    if(dd>k) return;
    if(dd==k){
        ans=min(ans,d);
        return;
    }
    if(path[k-dd].s==c) ans=min(ans,path[k-dd].f+d);
    for(pii i:adj[x]){
        if(i.f==p||vis[i.f]) continue;
        dfssolve(i.f,x,d+1,dd+i.s,c);
    }
    q.push({d,dd});
}

int getcentroid(int x){
    dfssiz(x,-1);
    return dfsget(x,-1,x);
}

void solve(int x){
    if(vis[x]) return;
    int c=getcentroid(x);

    path[0]={0,c};
    pii cur;
    for(pii i:adj[c]){
        if(vis[i.f]) continue;
        dfssolve(i.f,c,1,i.s,c);
        while(!q.empty()){
            cur=q.front();
            q.pop();
            if(path[cur.s].s!=c) path[cur.s]={cur.f,c};
            else path[cur.s].f=min(cur.f,path[cur.s].f);
        }
    }

    vis[c]=1;
    for(pii i:adj[c]){
        if(vis[i.f]) continue;
        solve(i.f);
    }
}

signed best_path(signed N,signed K,signed H[][2],signed L[]){
    n=N;k=K;
    ans=LLONG_MAX;
    memset(path,0xff,sizeof(path));
    for(int i=0;i<n-1;i++){
        adj[H[i][0]].pb({H[i][1],L[i]});
        adj[H[i][1]].pb({H[i][0],L[i]});
    }
    solve(0);
    if(ans==LLONG_MAX) return -1;
    return ans;
}

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