제출 #938049

#제출 시각아이디문제언어결과실행 시간메모리
938049asdasdqwer도시들 (IOI15_towns)C++14
0 / 100
59 ms1628 KiB
#include "towns.h" #include <bits/stdc++.h> using namespace std; #define pii array<int,2> vector<vector<int>> dis; map<pii,int> mp; int query(int a, int b) { if (mp.find({a,b}) != mp.end()) { return mp[{a,b}]; } if (mp.find({b,a}) != mp.end()) { return mp[{b,a}]; } int d = getDistance(a, b); mp[{a,b}] = d; return d; } int hubDistance(int N, int sub) { dis.assign(N, vector<int>(N, 1e9)); for (int i=0;i<N;i++) { dis[i][i] = 0; } // first N queries vector<int> lst(N); for (int i=0;i<N;i++) { lst[i] = i; } random_shuffle(lst.begin(), lst.end()); for (int i=0;i<N;i++) { int a = lst[i]; int b = lst[(i+1)%N]; dis[a][b] = dis[b][a] = query(a,b); } // floyd warshall for (int k=0;k<N;k++) { for (int i=0;i<N;i++) { for (int j=0;j<N;j++) { dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); } } } bool found = false; int retVal = 0; pii foundPos; while (!found) { // find maximum value and respective nodes int mxVal = -1; pii pos = {-1, -1}; for (int i=0;i<N;i++) { for (int j=i+1;j<N;j++) { if (dis[i][j] > mxVal) { mxVal = dis[i][j]; pos = {i, j}; } } } int d = query(pos[0], pos[1]); if (d == dis[pos[0]][pos[1]]) { found = true; retVal = d; foundPos = pos; break; } dis[pos[0]][pos[1]] = dis[pos[1]][pos[0]] = d; for (int i=0;i<N;i++) { dis[i][pos[0]] = min(dis[i][pos[0]], dis[i][pos[1]] + dis[pos[1]][pos[0]]); dis[i][pos[1]] = min(dis[i][pos[1]], dis[i][pos[0]] + dis[pos[0]][pos[1]]); } } int mxDis = retVal; for (int i=0;i<N;i++) { if (i == foundPos[0] || i == foundPos[1]) continue; int q1 = query(foundPos[0], i); int q2 = query(foundPos[1], i); int sum = q1 + q2; int weightTo = (sum - retVal) / 2; mxDis = min(mxDis, max(q1 - weightTo, q2 - weightTo)); } return mxDis; }

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:24:28: warning: unused parameter 'sub' [-Wunused-parameter]
   24 | 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...