| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 970383 | vjudge1 | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
#pragma GCC optimize("Ofast")
void YES()
{
cout<<"YES\n";
}
void NO()
{
cout<<"NO\n";
}
ll n;
ll answer = 1e18;
vector<ll> cnt;
vector<ll> par;
vector<ll> dist;
vector<vector<ll>> st;
vector<ll> tin;
vector<ll> ins;
vector<ll> first;
vector<ll> inv;
vector<ll> po(200001);
vector<ll> val;
ll T = 0;
void dfs2(ll v,vector<vector<vector<ll>>> & ed)
{
tin[v] = ++T;
inv[T] = v;
first[v] = ins.size();
ins.push_back(tin[v]);
for (vector<ll> i : ed[v])
{
ll u = i[0];
if (!tin[u])
{
dist[u] = dist[v]+i[1];
dfs2(u,ed);
ins.push_back(tin[v]);
}
}
}
void dfs(ll v,ll pr,vector<vector<vector<ll>>> & ed)
{
cnt[v] = 1;
for (vector<ll> i : ed[v])
{
ll u = i[0];
if (par[u] != -1 || u == pr) continue;
dfs(u,v,ed);
cnt[v]+=cnt[u];
}
}
ll cent(ll v,ll pr,ll s,vector<vector<vector<ll>>> & ed)
{
for (vector<ll> i : ed[v])
{
ll u = i[0];
if (u != pr && par[u] == -1 && cnt[u] > s/2)
{
return cent(u,v,s,ed);
}
}
return v;
}
ll decomp(ll v,vector<vector<vector<ll>>> & ed)
{
dfs(v,-1,ed);
ll s = cnt[v];
ll c = cent(v,-1,s,ed);
// cout<<c+1<<" ";
par[c] = -2;
for (vector<ll> i : ed[c])
{
ll u = i[0];
if (par[u] == -1)
{
par[decomp(u,ed)] = c;
}
}
return c;
}
ll findlca(ll a,ll b)
{
a = first[a],b = first[b];
if (a > b) swap(a,b);
ll k = po[b-a+1];
return inv[min(st[k][a],st[k][b-(1 << k)+1])];
}
ll finddist(ll u,ll v)
{
ll lca = findlca(u,v);
return dist[u]+dist[v]-2*dist[lca];
}
void paint(ll v,ll u)
{
if (v == -2) return;
val[v] = min(val[v],finddist(u,v));
paint(par[v],u);
}
ll find(ll v,ll u)
{
if (v == -2) return 1e18;
return min(find(par[v],u),val[v]+finddist(u,v));
}
ll best_path(ll n,ll k,vector<vector<ll>> H,vector<ll> L)
{
tin = vector<ll>(n,0);
cnt = vector<ll>(n,0);
par = vector<ll>(n,-1);
first = vector<ll>(n,0);
dist = vector<ll>(n,0);
inv = vector<ll>(n+1,0);
val = vector<ll>(n,1e18);
st = vector<vector<ll>>(2*n,vector<ll>(0));
vector<vector<vector<ll>>> ed(n);
for (ll e = 0;e<n-1;e++)
{
ll u = H[e][0]-1,v = H[e][1]-1,we = L[e];
ed[u].push_back({v,we});
ed[v].push_back({u,we});
}
decomp(0,ed);
dfs2(0,ed);
answer = 1e18;
for (ll e = 0;e<ins.size();e++)
{
st[0].push_back(ins[e]);
}
for (ll k = 1;k<20;k++)
{
ll po = (1 << (k-1));
for (ll e = 0;e<ins.size()-po*2+1;e++)
{
st[k].push_back(min(st[k-1][e],st[k-1][e+po]));
}
}
return answer;
}
void ans()
{
// ll n,k;cin>>n>>k;
// vector<vector<ll>> H(n-1);
// vector<ll> L(n-1);
// for (ll e = 0;e<n-1;e++)
// {
// ll u,v;cin>>u>>v;
// H[e] = {u,v};
// }
// for (ll e = 0;e<n-1;e++)
// {
// ll we;cin>>we;
// L[e] = we;
// }
// cout<<best_path(n,k,H,L)<<"\n";
}
int main()
{
ll p = 0,d = 1;
for (ll e = 1;e<=200000;e++)
{
if (e == d*2)
{
p++;
d*=2;
}
po[e] = p;
}
cin.tie(0);cout.tie(0);
ios_base::sync_with_stdio(0);
ll t = 1;
for (ll e = 1;e<=t;e++)
{
ans();
}
return 0;
}