제출 #207537

#제출 시각아이디문제언어결과실행 시간메모리
207537AQT도시들 (IOI15_towns)C++14
25 / 100
30 ms504 KiB
#include <towns.h> #include <bits/stdc++.h> using namespace std; int dist[2][200]; int par[200], sz[200]; bool midset[200]; int graph[200][200]; /* int getDistance(int i, int j){ //cout << "? " << i << " " << j << endl; //int k; //cin >> k; //return k; return graph[i][j]; } */ int hubDistance(int N, int sub){ int d1 = 0, d2 = 0; for(int i = 1; i<N; i++){ dist[0][i] = getDistance(0, i); if(dist[0][i] > dist[0][d1]){ d1 = i; } } for(int i = 0; i<N; i++){ dist[1][i] = getDistance(d1, i); if(dist[1][i] > dist[1][d2]){ d2 = i; } } int dia = dist[1][d2]; //cout << "diameter endpoints: " << d1 << " " << d2 << endl; int ans = dia; for(int i = 0; i<N; i++){ int k = (dist[0][d1] + dist[1][i] - dist[0][i])/2; //cout << "which set?: " << i << " " << k << endl; if(abs(ans-dia/2) > abs(k-dia/2)){ ans = k; } midset[i] = 0; } int d = ans; ans = max(ans, dia-ans); int lft = 0, rht = 0; for(int i = 0; i<N; i++){ int k = (dist[0][d1] + dist[1][i] - dist[0][i])/2; //cout << "which set again?: " << i << " " << k << endl; //cout << dist[0][d1] << " " << dist[1][i] << " " << dist[0][i] << endl; if(dia-k > ans){ //cout << "lft: " << i << endl; midset[i] = 1; lft++; } else if(k > ans){ //cout << "rht: " << i << endl; midset[i] = 1; rht++; } } if(max(lft, rht) > N/2){ ans = -ans; return ans; } /* vector<int> v, w; for(int i =0 ; i<N; i++){ if(midset[i]){ par[i] = -1; sz[i] = 0; continue; } par[i] = i; v.push_back(i); sz[i] = 1; } int g = -1; while(v.size()){ //cout << "next iteration: " << k << endl; random_shuffle(v.begin(), v.end()); while(v.size() >= 2){ int n = v.back(); v.pop_back(); int m = v.back(); v.pop_back(); //cout << dist[1][n] + dist[1][m] - getDistance(n, m) << " " << 2*d << endl; if(dist[1][n] + dist[1][m] - getDistance(n, m) > 2*d){ par[n] = -1; sz[m] += sz[n]; w.push_back(m); } } if(v.size() == 1 && w.empty()){ g = v[0]; break; } swap(v, w); w.clear(); } //cout << g << endl; if(g != -1){ int cnt = 0; for(int i = 0; i<N; i++){ if(par[i] == i && !midset[i]){ if(dist[1][i] + dist[1][g] - getDistance(i, g) > 2*d){ cnt += sz[i]; //cout << "sz: " << i << " " << sz[i] << endl; } } } //cout << cnt << endl; if(cnt > N/2){ ans = -ans; } } */ /* int g = -1, cnt = 0; for(int i = 0; i<N; i++){ if(midset[i]){ continue; } if(cnt == 0){ g = i; cnt = 1; } else if(dist[1][i] + dist[1][g] - getDistance(i, g) > 2*d){ cnt++; } else{ cnt--; if(cnt == 0){ g = -1; } } //cout << i << " " << cnt << endl; } //cout << "g: " << g << endl; if(g != -1){ cnt = 0; for(int i = 0; i<N; i++){ if(!midset[i] && dist[1][i] + dist[1][g] - getDistance(i, g) > 2*d){ cnt++; } } //cout << cnt << endl; if(cnt > N/2){ ans = -ans; } } */ vector<int> v, w; for(int i = 0; i<N; i++){ if(midset[i]){ continue; } if(v.empty() || dist[1][i] + dist[1][v.back()] - getDistance(i, v.back()) > 2*d){ v.push_back(i); if(w.size()){ v.push_back(w.back()); w.pop_back(); } } else{ w.push_back(i); } } int g = v.back(); v.pop_back(); int cnt = 1; while(v.size()){ if(dist[1][v.back()] + dist[1][g] - getDistance(v.back(), g) > 2*d){ v.pop_back(); if(v.size()){ v.pop_back(); } } else if(w.empty()){ return ans; } else{ v.pop_back(); w.pop_back(); } } return -ans; } /* int main(){ int tempN, sub, T; cin >> sub >> T; while(T--){ cin >> tempN; for(int i =0 ; i<tempN; i++){ for(int j = 0; j<tempN; j++){ cin >> graph[i][j]; } } cout << hubDistance(tempN, sub) << endl; } } */

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:173:9: warning: unused variable 'cnt' [-Wunused-variable]
     int cnt = 1;
         ^~~
towns.cpp:21:28: warning: unused parameter 'sub' [-Wunused-parameter]
 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...