제출 #349903

#제출 시각아이디문제언어결과실행 시간메모리
349903pit4h도시들 (IOI15_towns)C++14
0 / 100
19 ms748 KiB
#include<bits/stdc++.h> #include "towns.h" using namespace std; const int MAXN = 111; int dist[MAXN][MAXN]; int n, subtask; int l=-1, r=-1; int queries; int GetDistance(int i, int j) { queries++; return getDistance(i, j); } int dist_to_lca(int i, int j, int k) { return dist[i][k] - (dist[i][k] + dist[j][k] - dist[i][j])/2; } int dist_to_hub(int i, int j, int d) { return dist[i][j] - d; } bool is_balanced(vector<int> vec, int rt, int d) { if((int)vec.size() <= n/2) return true; vector<int> cand; vector<bool> popped(n), is_leader(n); for(int i: vec) { if(cand.empty()) { cand.push_back(i); } else { if(GetDistance(cand.back(), i) < dist_to_hub(cand.back(), rt, d) + dist_to_hub(i, rt, d)) { popped[i] = 0; cand.push_back(i); } else { popped[i] = 1; cand.pop_back(); } } } if(cand.empty()) { return true; } int leader = cand.back(); is_leader[leader] = 1; cand.clear(); int cnt = 0; for(int i: vec) { if(cand.empty()) { cand.push_back(i); if(GetDistance(i, leader) < dist_to_hub(i, rt, d) + dist_to_hub(leader, rt, d)) { cnt++; is_leader[i] = 1; } } else { if(!popped[i]) { if(is_leader[cand.back()]) { cnt++; is_leader[i] = 1; } cand.push_back(i); } else { if(GetDistance(i, leader) < dist_to_hub(i, rt, d) + dist_to_hub(leader, rt, d)) { cnt++; is_leader[i] = 1; } cand.pop_back(); } } } if(cnt <= n/2) return true; else return false; } int hubDistance(int N, int sub) { subtask = sub; n = N; for(int i=1; i<n; ++i) { dist[0][i] = GetDistance(0, i); dist[i][0] = dist[0][i]; if(l==-1 || dist[0][i] > dist[0][l]) { l = i; } } for(int i=0; i<n; ++i) { if(i==l) continue; dist[l][i] = GetDistance(l, i); dist[i][l] = dist[l][i]; if(r==-1 || dist[l][i] > dist[l][r]) { r = i; } } int R = 1e9+1; vector<vector<int>> half(2, vector<int>()); vector<bool> is_hub(2); for(int i=0; i<n; ++i) { int dl = dist_to_lca(l, 0, i); int rc = max(dl, dist[l][r] - dl); if(rc < R) { is_hub[0] = is_hub[1] = 0; } R = min(R, rc); if(rc==R) { is_hub[dl >= (dist[l][r]-1)/2+1] = 1; } if(dl < (dist[l][r]-1)/2+1) { half[0].push_back(i); } else { half[1].push_back(i); } } return R; if((is_hub[0] && is_balanced(half[0], 0, dist[0][l] - (dist[l][r] - R)) && (int)half[1].size() <= n/2) || (is_hub[1] && is_balanced(half[1], l, R) && (int)half[0].size() <= n/2)) { return R; } else { return -R; } }
#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...