| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 744833 | myrcella | 도시들 (IOI15_towns) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
const int maxn = 111;
#include "towns.h"
int grid[maxn][maxn];
int getDistance(int x,int y) {return grid[x][y];}
int u=0,R;
int dis[maxn][maxn];
int getdis(int x,int y) {
if (x==y) return 0;
if (dis[x][y]==-1) dis[x][y] = dis[y][x] = getDistance(x,y);
return dis[x][y];
}
bool samebranch(int x,int y) {
return getdis(x,u) + getdis(y,u) - getdis(x,y) > 2*R;
}
int hubDistance(int N, int sub) {
memset(dis,-1,sizeof(dis));
rep(i,0,N) if (getdis(0,i) > getdis(0,u)) u = i;
int diam = 0;
rep(i,0,N) diam = max(diam,getdis(i,u));
int ans = mod;
//find centre
vector <pii> node;
rep(i,0,N) {
int disi0 = getdis(i,0), disu0 = getdis(u,0), disui = getdis(u,i);
int cur = (disu0 + disui - disi0)/2;
assert((disu0+disui-disi0)%2==0);
node.pb({cur,i});
ans = min(ans,max(cur,diam-cur));
}
int cnt = 0;
sort(ALL(node));
while (max(node.back().fi,diam-node.back().fi)!=ans) cnt++,node.pop_back();
if (cnt*2>N) return -ans;
cnt = 0;
reverse(ALL(node));
while (max(node.back().fi,diam-node.back().fi)!=ans) cnt++,node.pop_back();
if (cnt*2>N) return -ans;
vector <pii> alive,dead;
R = node[0].fi;
for (auto it:node) alive.pb({it.se,1});
while (1) {
if (SZ(alive)==1) {
int tmp = alive[0].se;
if (tmp*2>N) return -ans;
for (auto it:dead) if (samebranch(it.fi,alive[0].fi)) {
tmp+=it.se;
if (tmp*2>N) return -ans;
}
return ans;
}
if (SZ(alive)%2==1) {
dead.pb(alive.back());
alive.pop_back();
}
if (alive.empty()) return ans;
vector <pii> tmp;
while (!alive.empty()) {
auto it1 = alive.back();alive.pop_back();
auto it2 = alive.back();alive.pop_back();
if (samebranch(it1.fi,it2.fi)) {
tmp.pb({it1.fi,it1.se + it2.se});
if ((it1.se + it2.se)*2>N) return -ans;
}
else dead.pb(it1),dead.pb(it2);
}
alive = tmp;
}
}