Submission #744864

#TimeUsernameProblemLanguageResultExecution timeMemory
744864myrcellaTowns (IOI15_towns)C++17
0 / 100
12 ms468 KiB
//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 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) { if (getdis(x,u) + getdis(y,u) - getdis(x,y) > 2*R) return true; else assert(getdis(x,u) + getdis(y,u) - getdis(x,y) == 2*R); return false; } int hubDistance(int N, int sub) { u = 0; 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}); /* for (auto it:node) { cnt = 0; for (auto itt:node) if (samebranch(it.se,itt.se)) cnt++; if (cnt*2>N) debug(it.se); } */ pii hi = {-1,-1}; while (1) { if (SZ(alive)%2==1) { if (hi.fi==-1) { hi = alive.back(); alive.pop_back(); } else alive.pb(hi); } if (alive.empty()) break; 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; } if (hi.fi==-1) return -ans; cnt = hi.se; if (cnt*2>N) return -ans; for (auto it:dead) { if (samebranch(it.fi,hi.fi)) { cnt += it.se; if (cnt*2>N) return -ans; } } return ans; }

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:44:28: warning: unused parameter 'sub' [-Wunused-parameter]
   44 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...