제출 #861188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
861188		8pete8	경주 (Race) (IOI11_race)	C++14	0 / 100	44 ms	18268 KiB

race

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset> 
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<ll,ll>
#define pppiiii pair<pii,pii>
#define ppii pair<ll,pii>
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
const int mxn=1e5+1,mx=1e6;
ll inf=1e18;
vector<pii>adj[mxn+10];
ll sz[mxn+10],n,k;
ll mn[mx+10];
pii dist[mx+10];
ll ans=inf;
bitset<mxn+10>del;
void dfs(int cur,int p){
    for(auto i:adj[cur]){
        if(i.f!=p&&(!del[i.f]))dfs(i.f,cur),sz[cur]+=sz[i.f];
    }
}
int getcen(int cur,int p){
	for(auto i:adj[cur]){
		if(i.f==p||del[i.f])continue;
		if(sz[i.f]*2>n)return getcen(i.f,cur);
	}
	return cur;
}
void solve(int cur,int p){
    mn[dist[cur].f]=min(mn[dist[cur].f],dist[cur].s);
	for(auto i:adj[cur]){
		if(i.f==p||del[i.f])continue;
		dist[i.f].f=dist[cur].f+i.s;
		dist[i.f].s=dist[cur].s+1;
		solve(i.f,cur);
	}
}
void decomp(int cur){
    fill(sz,sz+mxn,1);
    fill(mn,mn+mx+1,inf);
    fill(dist,dist+mxn+1,make_pair(0,0));
    dfs(cur,-1);
    int node=getcen(cur,-1);
    solve(node,-1);
    if(mn[k]!=inf)ans=min(ans,mn[k]);
    for(int i=1;i<k;i++){
        if(mn[i]==inf||mn[k-i]==inf)continue;
        ans=min(ans,mn[i]+mn[k-i]);
    }
    del[node]=true;
    for(auto i:adj[node])if(!del[i.f])decomp(i.f);
}
int best_path(int N, int K, int H[][2], int L[]){
	n=N;
    k=K;
	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]});
	}
    decomp(0);
    if(ans==inf)ans=-1;
    return ans;
}/*
int main(){
    cin>>n>>k;
    int h[n][2],l[n];
    for(int i=0;i<n-1;i++)cin>>h[i][0]>>h[i][1]>>l[i];
    cout<<best_path(n,k,h,l);
}*/

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