#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define st first
#define nd second
#define pb push_back
#define pq priority_queue
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mxn = 1003;
mt19937 _rand(time(NULL));
clock_t z;
#include "citymapping.h"
ll dist[mxn][mxn];/*
ll get_distance(int x, int y){
cout<<"? "<<x<<' '<<y<<endl;
ll ret;
cin >> ret;
return ret;
}*/
ll ask(int x, int y){
if(x != y && dist[x][y] == 0){
dist[x][y] = dist[y][x] = get_distance(x+1, y+1);
}
return dist[x][y];
}
vector<int> g;
int R1, R2;
int AA[mxn], BB[mxn], WW[mxn];
int edge_id = 0;
void add_edge(int x, int y, int w){
AA[edge_id] = x;
BB[edge_id] = y;
WW[edge_id] = w;
edge_id ++;
}
void decompose(vector<int> v){
int r1 = v[_rand() % (int)v.sized()];
g = v;
if((int)g.size() <= 1) return;
for(auto u : g){
ask(u, r1);
}
int r2 = r1;
for(auto u : g){
if(dist[r1][u] > dist[r1][r2]){
r2 = u;
}
}
//r1 -> r2 initial diameter
for(auto u : g){
ask(u, r2);
}
R1 = r1;
R2 = r2;
sort(all(g), [](const int &i, const int &j){
return dist[R1][i] < dist[R1][j];
});
vector<int> diam;
for(auto u : g){
if(dist[r1][u] + dist[u][r2] == dist[r1][r2]){
diam.pb(u);
}
}
fr(i, 1, (int)diam.size()){
add_edge(diam[i-1], diam[i], dist[r1][diam[i]] - dist[r1][diam[i-1]]);
}
vector<int> sub[(int)diam.size()];
fr(i, 0, (int)diam.size()){
sub[i].pb(diam[i]);
}
for(auto u : g){
if(dist[r1][u] + dist[u][r2] == dist[r1][r2]) continue;
fr(i, 0, (int)diam.size()){
auto d = diam[i];
if(dist[r1][u] - dist[r2][u] == dist[r1][d] - dist[r2][d]){
sub[i].pb(u);
break;
}
}
}
fr(i, 0, (int)diam.size()){
auto d = diam[i];
for(auto s : sub[i]){
dist[d][s] = dist[r1][s] - dist[r1][d];
}
}
fr(i, 0, (int)diam.size()){
decompose(sub[i]);
}
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
vector<int> v;
fr(i, 0, N) v.pb(i);
/*int r1 = 0;
fr(i, 0, N){
ask(0, i);
if(dist[0][i] > dist[0][r1]) r1 = i;
}*/
decompose(v);
fr(i, 0, N-1){
A[i] = AA[i] + 1;
B[i] = BB[i] + 1;
W[i] = WW[i];
//cout<<A[i]<<' '<<B[i]<<' '<<W[i]<<endl;
}
return;
}/*
int A[100], B[100], W[100];
int main(){
find_roads(5, 0, A, B, W);
}
*/
Compilation message
citymapping.cpp: In function 'void decompose(std::vector<int>)':
citymapping.cpp:50:30: error: 'class std::vector<int>' has no member named 'sized'; did you mean 'size'?
50 | int r1 = v[_rand() % (int)v.sized()];
| ^~~~~
| size
