제출 #795420

#제출 시각아이디문제언어결과실행 시간메모리
795420jasmin도시들 (IOI15_towns)C++17
25 / 100
15 ms484 KiB
#include "towns.h" #include<bits/stdc++.h> using namespace std; vector<int> dist0; int a=-1; vector<int> dista; int b=-1; vector<int> distb; int Distance(int i, int j){ if(j<i) swap(i, j); if(i==0) return dist0[j]; if(i==a) return dista[j]; if(i==b) return distb[j]; if(j==a) return dista[i]; if(j==b) return distb[i]; return getDistance(i, j); } bool balancedSlow(int n, int r, int diameter, map<int, vector<int> >& group, vector<int>& dista){ bool balanced_hub=false; int cntleft=1; for(auto [x, g]: group){ if(max(x, diameter-x)!=r){ //no hub continue; } int cntright = n - cntleft - (int)g.size(); if(cntleft>n/2 || cntright>n/2) continue; vector<bool> vis(n, false); int open = (int)g.size(); bool balanced=true; while(open > n/2){ int v=g.back(); g.pop_back(); if(vis[v]){ continue; } vis[v]=true; int size=1; for(auto u: g){ int d = Distance(v, u); if(d < dista[v]-x + dista[u]-x){ //same component vis[u]=true; size++; } } if(size > n/2){ balanced = false; break; } open -= size; } if(balanced){ balanced_hub = true; break; } cntleft += (int)group.size(); } return balanced_hub; } int hubDistance(int n, int sub) { //find diameter vector<int> dist0(n); int a=1; for(int i=1; i<n; i++){ dist0[i] = getDistance(0, i); if(dist0[i]>dist0[a]){ a=i; } } int b=0; vector<int> dista(n); dista[0] = dist0[a]; for(int i=1; i<n; i++){ if(i==a) continue; dista[i] = getDistance(a, i); if(dista[i] > dista[b]){ b=i; } } vector<int> distb(n); distb[0] = dist0[b]; distb[a] = dista[b]; for(int i=1; i<n; i++){ if(i==a || i==b) continue; distb[i] = getDistance(b, i); } int diameter = dista[b]; //group the leafes vector<int> dleft(n); dleft[a]=0; dleft[b]=diameter; vector<int> ddiam(n); ddiam[a]=ddiam[b]=0; map<int, vector<int> > group; for(int i=0; i<n; i++){ if(i==a || i==b) continue; ddiam[i] = (dista[i]+distb[i] - diameter)/2; dleft[i] = dista[i]-ddiam[i]; group[dleft[i]].push_back(i); } //compute r int r=diameter; for(auto [x, g]: group){ r = min(r, max(x, diameter-x)); } bool balanced = false; if(2<sub){ balanced = balancedSlow(n, r, diameter, group, dista); } if(balanced){ return r; } return -r; }

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

towns.cpp: In function 'bool balancedSlow(int, int, int, std::map<int, std::vector<int> >&, std::vector<int>&)':
towns.cpp:26:91: warning: declaration of 'dista' shadows a global declaration [-Wshadow]
   26 | bool balancedSlow(int n, int r, int diameter, map<int, vector<int> >& group, vector<int>& dista){
      |                                                                              ~~~~~~~~~~~~~^~~~~
towns.cpp:8:13: note: shadowed declaration is here
    8 | vector<int> dista;
      |             ^~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:81:17: warning: declaration of 'dist0' shadows a global declaration [-Wshadow]
   81 |     vector<int> dist0(n);
      |                 ^~~~~
towns.cpp:5:13: note: shadowed declaration is here
    5 | vector<int> dist0;
      |             ^~~~~
towns.cpp:82:9: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   82 |     int a=1;
      |         ^
towns.cpp:7:5: note: shadowed declaration is here
    7 | int a=-1;
      |     ^
towns.cpp:91:9: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   91 |     int b=0;
      |         ^
towns.cpp:10:5: note: shadowed declaration is here
   10 | int b=-1;
      |     ^
towns.cpp:92:17: warning: declaration of 'dista' shadows a global declaration [-Wshadow]
   92 |     vector<int> dista(n);
      |                 ^~~~~
towns.cpp:8:13: note: shadowed declaration is here
    8 | vector<int> dista;
      |             ^~~~~
towns.cpp:104:17: warning: declaration of 'distb' shadows a global declaration [-Wshadow]
  104 |     vector<int> distb(n);
      |                 ^~~~~
towns.cpp:11:13: note: shadowed declaration is here
   11 | vector<int> distb;
      |             ^~~~~
#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...