#include "citymapping.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
const int MAXN = 1005;
lint mem[MAXN][MAXN];
lint dist(int x, int y){
if(x == y) return 0;
if(mem[x][y]) return mem[x][y];
return mem[x][y] = mem[y][x] = get_distance(x, y);
}
vector<pi> gph[MAXN];
lint dep[MAXN];
bool vis[MAXN];
vector<int> dfn;
int sz[MAXN], msz[MAXN], par[MAXN];
void dfs(int x, int p){
sz[x] = 1;
msz[x] = 0;
for(auto &i : gph[x]){
if(!vis[i.second] && i.second != p){
dfs(i.second, x);
sz[x] += sz[i.second];
msz[x] = max(msz[x], sz[i.second]);
}
}
dfn.push_back(x);
}
int get_center(int v){
dfn.clear();
dfs(v, -1);
pi ret(1e9, -1);
for(auto &i : dfn){
pi ans = pi(max(sz(dfn) - sz[i], msz[i]), i);
ret = min(ret, ans);
}
return ret.second;
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
auto make_edge = [&](int s, int e, int x){
// printf("make_edge(%d, %d, %d)\n", s, e, x);
gph[s].emplace_back(x, e);
gph[e].emplace_back(x, s);
for(int i=0; i<N-1; i++){
if(!W[i]){
tie(A[i], B[i], W[i]) = make_tuple(s, e, x);
break;
}
}
};
vector<pi> v;
for(int i=2; i<=N; i++){
dep[i] = dist(1, i);
v.emplace_back(dep[i], i);
}
sort(v.begin(), v.end());
vector<int> prv = {1};
for(auto &i : v){
if(sz(prv) == 1){
par[i.second] = 1;
make_edge(1, i.second, i.first);
prv.push_back(i.second);
continue;
}
memset(vis, 0, sizeof(vis));
int cur_check = 1;
pi lowest(dep[1], 1);
while(cur_check && !vis[cur_check]){
int c = get_center(cur_check);
cout << c << endl;
vis[c] = 1;
vector<int> sons;
for(auto &j : gph[c]){
if(!vis[j.second] && dep[j.second] > dep[c]){
sons.push_back(j.second);
}
}
if(sons.empty()){
if(dist(1, c) + dist(c, i.second) == dist(1, i.second)){
lowest = max(lowest, pi(dep[c], c));
break;
}
else cur_check = par[c];
continue;
}
int next_trial = sons[0];
lint d1 = dep[next_trial];
lint d2 = dist(next_trial, i.second);
lint d3 = dep[i.second];
if(d1 + d2 == d3){
lowest = max(lowest, pi(dep[next_trial], next_trial));
cur_check = next_trial;
continue;
}
lint branch = (d1 + d2 - d3) / 2;
if(d1 - branch < dep[c]){
cur_check = par[c];
}
else{
lowest = max(lowest, pi(dep[c], c));
if(sz(sons) >= 2){
cur_check = sons[1];
}
if(sz(sons) == 3){
if(dist(1, sons[2]) + dist(sons[2], i.second) == dist(1, i.second)){
cur_check = sons[2];
}
}
}
}
make_edge(lowest.second, i.second, dist(lowest.second, i.second));
par[i.second] = lowest.second;
prv.push_back(i.second);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
8440 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
8440 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
8388 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
8388 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
8440 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
