| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 714105 | lam | 도시들 (IOI15_towns) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "towns.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "graderlib.c"
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
#define ff first
#define ss second
const int maxn = 110;
int n, root, m;
int d[maxn][maxn];
vector <ii> adj[maxn];
int s[maxn],id[maxn],nhanh,rt[maxn];
ii par[maxn];
bool cmp(ii x, ii y)
{
return s[x.ff]>s[y.ff];
}
void dfs(int x, int p)
{
s[x] = 1;
for (ii i:adj[x])
{
dfs(i.ff,x);
par[i.ff] ={x,i.ss};
s[x] += s[i.ff];
}
rt[x] = x;
sort(adj[x].begin(),adj[x].end(),cmp);
if (!adj[x].empty()) rt[x] = rt[adj[x][0].ff];
}
void build()
{
for (int i=0; i<m; i++) adj[i].clear(), rt[i] = -1, s[i] = 0;
for (int i=0; i<m; i++)
{
ii u = par[i];
if (u.ff==i||u.ff==-1) continue;
adj[u.ff].push_back({i,u.ss});
}
dfs(root,root);
}
int Ask(int u, int v)
{
if (u>v) swap(u,v);
if (d[u][v] == -1) d[u][v] = getDistance(u,v);
return d[u][v];
}
void addNode(int p, int w)
{
par[m++] = {p,w};
}
iii get(int a, int b, int c)
{
/**
d = lca(b,c);
**/
int ad = (Ask(a,b) + Ask(a,c) - Ask(b,c) ) /2;
int bd = Ask(a,b) - ad;
int cd = Ask(a,c) - ad;
cerr<<a<<' '<<b<<' '<<c<<" ?? "<<ad<<' '<<bd<<' '<<cd<<endl;
return {ad,{bd,cd}};
}
int hubDistance(int N, int sub) {
vector <int> a;
n=N; m=n;
for (int i=0; i<n; i++) a.push_back(i);
for (int i=0; i<n; i++)
for (int j=0; j<n; j++) d[i][j] = -1;
// random_shuffle(a.begin(),a.end());
for (int i=0; i<n; i++) par[i] = {-1,-1};
root = a[0];
iii temp = get(a[0],a[1],a[2]);
addNode(root,temp.ff);
par[1] = {m-1,temp.ss.ff};
par[2] = {m-1,temp.ss.ss};
// for (int j=0; j<m; j++) cerr<<par[j].ff<<','<<par[j].ss<<' '; cerr<<endl;
for (int i=3; i<n; i++)
{
build();
int x = root;
int dist_temp = 0;
while (true)
{
bool check = 1;
for (ii j:adj[x])
{
int v = j.ff;
iii temp = get(root,rt[v],a[i]);
if (temp.ff == dist_temp) continue;
int u = rt[v];
int dist = 0;
while (u!=x&&dist + par[u].ss <= temp.ss.ff)
{
dist+=par[u].ss;
u=par[u].ff;
}
// cerr<<x<<' '<<rt[v]<<' '<<a[i]<<" = "<<u<<' '<<par[u].ff<<','<<par[u].ss<<" : "<<temp.ss.ff<<' '<<dist<<endl;
if (dist == temp.ss.ff)
{
x=u; check = 0;
dist_temp = temp.ff;
par[a[i]] = {x,temp.ss.ss};
break;
}
else
{
addNode(par[u].ff,dist + par[u].ss - temp.ss.ff);
par[u] = {m-1, temp.ss.ff - dist};
x=u;
par[a[i]] = {m-1,temp.ss.ss};
check=1;
break;
}
}
if (check) break;
}
// for (int j=0; j<m; j++) cerr<<par[j].ff<<','<<par[j].ss<<' '; cerr<<endl;
}
build();
// for (int i=0; i<m; i++)
// {
// cerr<<i<<" := ";
// for (ii j:adj[i]) cerr<<j.ff<<','<<j.ss<<" "; cerr<<endl;
// }
}