제출 #1213974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213974		tuankhang13	Race (IOI11_race)	C++20	0 / 100	3 ms	6464 KiB

race

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
using namespace std;

const int maxn=2e5+13;
int n,k,res;
vector<pii> adj[maxn];
vector<int> del(maxn,0),child(maxn);
map<int,int> mp;

void dfs(int u,int p){
    child[u]=1;
    for(auto x:adj[u]){
        int v=x.fi;
        if(v!=p&&!del[v]){
            dfs(v,u);
            child[u]+=child[v];
        }
    }
}

int find_ctroid(int u,int p,int sz){
    for(auto x:adj[u]){
        int v=x.fi;
        if(v!=p&&!del[v]&&child[v]>sz/2){
            return find_ctroid(v,u,sz);
        }
    }
    return u;
}

void cointect(int u,int p,int depth,int dist, bool fil){
    if(dist>k)return;
    if(fil){
        if(mp.find(dist)!=mp.end()){
            mp[dist]=min(mp[dist],depth);
        }
        else{
            mp[dist]=depth;
        }
    }
    else {
        if(mp.find(k-dist)!=mp.end()){
            res=min(res,depth+mp[k-dist]);
        }
    }
    for(auto x:adj[u]){
        int v=x.fi;
        if(v!=p&&!del[v]){
            cointect(v,u,depth+1,dist+x.se,fil);
        }
    }
}

void decompose(int u){
    dfs(u,0);
    int ct=find_ctroid(u,0,child[u]);
    del[ct]=1;
    mp.clear();
    mp[0]=0;
    for(auto x:adj[ct]){
        int v=x.fi;
        if(!del[v]){
            cointect(v,ct,1,x.se,0);
            cointect(v,ct,1,x.se,1);
        }
    }

    for(auto x:adj[u]){
        int v=x.fi;
        if(!del[v]){
            decompose(v);
        }
    }
}

int best_path(int N,int K,int H[][2],int L[]){
    n=N; k=K;
    for(int i=0;i<n-1;++i){
        int u=H[i][0],v=H[i][1],w=L[i];
        ++u,++v;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    res=INT_MAX;
    decompose(1);
    return (res==INT_MAX?-1:res);
}

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