제출 #247333

#제출 시각아이디문제언어결과실행 시간메모리
247333tqbfjotld로카히아 유적 (FXCUP4_lokahia)C++17
0 / 100
7 ms948 KiB
#include "lokahia.h" #include <bits/stdc++.h> using namespace std; int NN; vector<int> thing[205]; int qLim = 400; int p[205]; int queried[205][205]; bool vis[205]; int root(int a){ return p[a]==a?a:p[a]=root(p[a]); } priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq; int sz[205]; int queryCount = 0; int query(int a, int b){ if (queryCount>=qLim){ return -1; } if (a==b) return a; if (a<0 || a>=NN || b<0 || b>=NN) return 1/0; if (queried[a][b]!=-1) return queried[a][b]; int res = CollectRelics(a,b); queryCount++; if (res!=-1){ thing[res].push_back(a); thing[res].push_back(b); //printf("add edge %d %d, %d %d\n",res,a,res,b); } queried[a][b] = res; return res; } int dfs(int node){ vis[node] = true; int res = 1; for (auto x : thing[node]){ if (!vis[x]){ res += dfs(x); } } return res; } int FindBase(int N){ memset(queried,-1,sizeof(queried)); NN = N; if (N==1) return 0; for (int x = 0; x<N; x++){ pq.push({1,x}); p[x] = x; } int mn = -1; vector<int> mns; while (!pq.empty()){ if (pq.size()<3){ if (pq.size()==1) {mns.push_back(pq.top().second);pq.pop();} else{ auto a = pq.top(); pq.pop(); auto b = pq.top(); pq.pop(); int r = query(root(a.second),root(b.second)); if (r==-2) return -1; if (r==-1){ mns.push_back(a.second); mns.push_back(b.second); } else{ if (root(a.second)!=root(r)){ sz[root(r)] += sz[root(a.second)]; p[root(a.second)] = r; } if (root(b.second)!=root(r)){ sz[root(r)] += sz[root(b.second)]; p[root(b.second)] = r; } pq.push({sz[root(r)],r}); } } continue; } auto a = pq.top(); pq.pop(); auto b = pq.top(); pq.pop(); auto c = pq.top(); pq.pop(); int res = query(root(a.second),root(b.second)); if (res==-2) return -1; if (res==-1){ int r2 = query(root(a.second),root(c.second)); if (r2==-2) return -1; if (r2==-1) { int r3 = query(root(b.second),root(c.second)); if (r3==-2) return -1; if (r3!=-1){ if (root(b.second)!=root(r3)){ sz[root(r3)] += sz[root(b.second)]; p[root(b.second)] = r3; } if (root(c.second)!=root(r3)){ sz[root(r3)] += sz[root(c.second)]; p[root(c.second)] = r3; } pq.push({sz[root(r3)],r3}); } else{ if (pq.empty()){ mns.push_back(a.second); mns.push_back(b.second); mns.push_back(c.second); } } } else{ if (root(a.second)!=root(r2)){ sz[root(r2)] += sz[root(a.second)]; p[root(a.second)] = r2; } if (root(c.second)!=root(r2)){ sz[root(r2)] += sz[root(c.second)]; p[root(c.second)] = r2; } pq.push({sz[root(r2)],r2}); } } else{ if (root(b.second)!=root(res)){ sz[root(res)] += sz[root(b.second)]; p[root(b.second)] = res; } if (root(a.second)!=root(res)){ sz[root(res)] += sz[root(a.second)]; p[root(a.second)] = res; } pq.push({sz[root(res)],res}); } } vector<pair<int,int> > mn2; for (int x = 0; x<N; x++){ mn2.push_back({sz[root(x)],x}); } sort(mn2.begin(),mn2.end(),greater<pair<int,int> >()); for (auto mnx : mn2){ int mn = mnx.second; for (int x = 0; x<N; x++){ if (root(x)!=root(mn)&&queryCount<qLim){ int res = query(root(x),root(mn)); if (res==-1) continue; p[root(x)] = res; p[root(mn)] = res; } } } for (int x = 0; x<N; x++){ for (int y = 0; y<N; y++){ vis[y] = false; } if (dfs(x)>N/2){ return x; } } return -1; }

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

lokahia.cpp: In function 'int query(int, int)':
lokahia.cpp:25:47: warning: division by zero [-Wdiv-by-zero]
     if (a<0 || a>=NN || b<0 || b>=NN) return 1/0;
                                              ~^~
lokahia.cpp: In function 'int FindBase(int)':
lokahia.cpp:57:6: warning: unused variable 'mn' [-Wunused-variable]
  int mn = -1;
      ^~
#Verdict Execution timeMemoryGrader output
Fetching results...