제출 #744990

#제출 시각아이디문제언어결과실행 시간메모리
744990myrcella도시들 (IOI15_towns)C++17
컴파일 에러
0 ms0 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,n; int dis[maxn][maxn]; vector <pii> nodee; 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,int R) { if (getdis(x,u) + getdis(y,u) - getdis(x,y) > 2*R) return true; assert(getdis(x,u) + getdis(y,u) - getdis(x,y) == 2*R); return false; } bool check(int R) { int cnt = 0; vector <pii> node = nodee; while (!node.empty() and node.back().fi!=R) cnt++,node.pop_back(); if (cnt*2>n) return false; cnt = 0; reverse(ALL(node)); while (!node.empty() and node.back().fi!=R) cnt++,node.pop_back(); if (cnt*2>n) return false; vector <pii> alive,dead; for (auto it:node) alive.pb({it.se,1}); /*for (auto it:node) { int cnt=0; for (auto itt:node) if (samebranch(it.se,itt.se,R)) { cnt++; //cout<<itt.se<<" "; } if (cnt*2>n) cout<<it.se<<" "; }*/ while (1) { if (SZ(alive)<=1) break; vector <pii> tmp; while (SZ(alive)>1) { auto it1 = alive.back();alive.pop_back(); auto it2 = alive.back();alive.pop_back(); if (samebranch(it1.fi,it2.fi,R)) { tmp.pb({it1.fi,it1.se + it2.se}); if ((it1.se + it2.se)*2>n) return false; } else { if (it1.se>it2.se) swap(it1,it2); if (it1.se==it2.se) dead.pb(it1),dead.pb(it2); else dead.pb(it1),dead.pb({it2.fi,it1.se}),tmp.pb({it2.fi,it2.se-it1.se}); } } while (!tmp.empty()) alive.pb(tmp.back()),tmp.pop_back(); } if (alive.empty()) return true; cnt = alive[0].se; if (cnt*2>n) return false; for (auto it:dead) { if (samebranch(it.fi,alive[0].fi,R)) { cnt += it.se; if (cnt*2>n) return false; } } return true; } int hubDistance(int N, int sub) { n = N; 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 nodee.clear(); 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); nodee.pb({cur,i}); ans = min(ans,max(cur,diam-cur)); } sort(ALL(nodee)); if (check(ans) or check(diam-ans)) return ans; else return -ans; } void _ini_query(int N,int subtask) { rep(i,0,N) rep(j,0,N) cin>>grid[i][j]; return; }

컴파일 시 표준 에러 (stderr) 메시지

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:95:28: warning: unused parameter 'sub' [-Wunused-parameter]
   95 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~
towns.cpp: In function 'void _ini_query(int, int)':
towns.cpp:119:19: error: 'grid' was not declared in this scope
  119 |   rep(j,0,N) cin>>grid[i][j];
      |                   ^~~~
towns.cpp:117:27: warning: unused parameter 'subtask' [-Wunused-parameter]
  117 | void _ini_query(int N,int subtask) {
      |                       ~~~~^~~~~~~