| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 201567 | blacktulip | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long lo;
typedef pair< lo,lo > PII;
#define fi first
#define int long long
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 100000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 1000005;
const lo mod = 1000000007;
int n,m,b[li],a[li],k,flag,t,sub[li],vis[li],cevap=inf,say;
int cev;
map<int,int> last,visit;
string s;
vector<PII> v[li];
inline void dfs(int node,int ata){
sub[node]=1;
for(int i=0;i<(int)v[node].size();i++){
int go=v[node][i].fi;
if(go==ata)continue;
if(vis[go]==1)continue;
dfs(go,node);
sub[node]+=sub[go];
}
}
inline int find_centroid(int node,int ata,int sz){
//~ int mx=0;
//~ int ind=0;
for(int i=0;i<(int)v[node].size();i++){
int go=v[node][i].fi;
if(vis[go]==1)continue;
if(go==ata)continue;
if(sub[go]>(sz)/2)return find_centroid(go,node,sz);
}
return node;
}
inline void dfs2(int node,int ata,int der,int co){
for(int i=0;i<(int)v[node].size();i++){
int go=v[node][i].fi;
if(go==ata)continue;
if(vis[go]==1)continue;
dfs2(go,node,der+1,co+v[node][i].se);
}
if(visit[k-co]==1){
cevap=min(cevap,last[k-co]+der);
}
}
inline void dfs1(int node,int ata,int der,int co){
for(int i=0;i<(int)v[node].size();i++){
int go=v[node][i].fi;
if(go==ata)continue;
if(vis[go]==1)continue;
dfs1(go,node,der+1,co+v[node][i].se);
}
if(visit[co]==0)last[co]=der;
visit[co]=1;
last[co]=min(last[co],der);
}
inline void solve(int node){
//~ say++;
//~ cout<<say<<endl;
visit.clear();
//~ FOR sub[node]=0;
//~ last.clear();
dfs(node,-1);
int c=find_centroid(node,-1,sub[node]);
for(int i=0;i<(int)v[c].size();i++) {
int go=v[c][i].first;
if(vis[go]) continue ;
dfs2(go,c,1,v[c][i].second);
dfs1(go,c,1,v[c][i].second);
}
if(visit[k]==1)
cevap=min(cevap,last[k]);
vis[c]=1;
//~ cout<<c<<endl;
//~ dfs()
for(int i=0;i<(int)v[c].size();i++){
if(vis[v[c][i].fi]==0)solve(v[c][i].fi);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
scanf("%lld %lld",&n,&k);
for(int i=0;i<n-1;i++){
int x,y,z;
scanf("%lld %lld %lld",&x,&y,&z);
v[H[i][0]].pb(mp(H[i][1],L[i]));
v[H[i][1]].pb(mp(H[i][0],L[i]));
}
solve(0);
if(cevap>=inf)cevap=-1;
return N;
}