#include<bits/stdc++.h>
#include "citymapping.h"
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
vector<pii>aaa[1009];
mt19937_64 rng(101094);
vector<int>cc[1009];
int f[1009];
long long d[1009][1009];
long long ask(int x,int y){
if (d[x][y]!=-1)return d[x][y];
return d[x][y]=d[y][x]=get_distance(x,y);
}
int fs(int u){
if (f[u]<0)return u;
return f[u]=fs(f[u]);
}
void unite(int u,int v,int w){
int u1=u,v1=v;
u=fs(u),v=fs(v);
if (u==v)return;
if (f[u]>f[v]){
swap(u,v);
swap(u1,v1);
}
f[u]+=f[v];
for (auto vx:cc[u]){
for (auto vy:cc[v]){
d[vx][vy]=d[vy][vx]=1ll*w+d[vx][u1]+d[vy][v1];
}
}
for (auto vx:cc[v]){
cc[u].pb(vx);
}
cc[v].clear();
}
bool add[1009];
vector<int>xd[1009];
void solve(vector<int>&tmp,int s,int t){
if (sz(tmp)<=1)return;
for (auto v:tmp)add[v]=0;
shuffle(all(tmp),rng);
s=tmp[0];
sort(all(tmp),[&](int i,int j){
return ask(s,i)<ask(s,j);
});
t=tmp.back();
vector<int>vertice;
for (auto v:tmp){
if (ask(s,v)+ask(t,v)==ask(s,t)){
vertice.pb(v);
add[v]=1;
}
}
sort(all(vertice),[&](int i,int j){
return ask(s,i)<ask(s,j);
});
auto add_edg=[&](int u,int v,int w){
aaa[u].pb({v,w});
aaa[v].pb({u,w});
d[u][v]=d[v][u]=w;
unite(u,v,w);
//cerr<<u<<" "<<v<<" "<<w<<'\n';
return;
};
for1(i,1,sz(vertice)-1){
add_edg(vertice[i],vertice[i-1],ask(vertice[i],s)-ask(vertice[i-1],s));
}
for(auto v:tmp){
if (add[v])continue;
for (auto u:vertice){
if (ask(s,v)-ask(s,u)==ask(t,v)-ask(t,u)&&ask(s,v)>ask(s,u)){
xd[u].pb(v);
}
}
}
for (auto u:vertice){
if (!xd[u].empty()){
sort(all(xd[u]),[&](int i,int j){
return ask(i,s)<ask(j,s);
});
for (auto v:xd[u]){
d[u][v]=d[v][u]=ask(v,s)-ask(u,s);
}
if (u!=s&&u!=t){
int news=xd[u][0],newt=xd[u].back();
add_edg(u,xd[u][0],d[u][xd[u][0]]);
for (auto v:xd[u]){
d[v][xd[u][0]]=d[xd[u][0]][v]=d[u][v]-d[u][xd[u][0]];
}
vector<int>cop;
cop.swap(xd[u]);
solve(cop,news,newt);
}
else {
vector<int>cop;
int news=u,newt=xd[u].back();
cop.swap(xd[u]);
cop.pb(u);
solve(cop,news,newt);
}
}
}
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
for1(i,1,N){
f[i]=-1;
cc[i].pb(i);
for1(j,1,N){
d[i][j]=-1;
}
d[i][i]=0;
}
vector<int>tree;
for1(i,1,N)tree.pb(i);
int s=rng()%N+1,t;
while (true){
t=rng()%N+1;
if (s==t)continue;
break;
}
solve(tree,s,t);
int cnt=0;
for1(i,1,N){
for (auto v:aaa[i]){
if (v.fi>i){
A[cnt]=v.fi,B[cnt]=i,W[cnt]=v.se;
cnt++;
}
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8536 KB |
Correct: 2254 out of 500000 queries used. |
2 |
Correct |
4 ms |
8792 KB |
Correct: 2680 out of 500000 queries used. |
3 |
Correct |
3 ms |
8564 KB |
Correct: 5222 out of 500000 queries used. |
4 |
Correct |
3 ms |
8540 KB |
Correct: 5680 out of 500000 queries used. |
5 |
Correct |
3 ms |
8540 KB |
Correct: 3414 out of 500000 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8536 KB |
Correct: 2254 out of 500000 queries used. |
2 |
Correct |
4 ms |
8792 KB |
Correct: 2680 out of 500000 queries used. |
3 |
Correct |
3 ms |
8564 KB |
Correct: 5222 out of 500000 queries used. |
4 |
Correct |
3 ms |
8540 KB |
Correct: 5680 out of 500000 queries used. |
5 |
Correct |
3 ms |
8540 KB |
Correct: 3414 out of 500000 queries used. |
6 |
Correct |
3 ms |
8540 KB |
Correct: 3040 out of 500000 queries used. |
7 |
Correct |
4 ms |
8540 KB |
Correct: 5817 out of 500000 queries used. |
8 |
Correct |
3 ms |
8540 KB |
Correct: 5981 out of 500000 queries used. |
9 |
Correct |
3 ms |
8540 KB |
Correct: 5791 out of 500000 queries used. |
10 |
Correct |
3 ms |
8540 KB |
Correct: 5451 out of 500000 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8536 KB |
Correct: 2108 out of 12000 queries used. |
2 |
Correct |
3 ms |
8536 KB |
Correct: 1994 out of 12000 queries used. |
3 |
Correct |
3 ms |
8640 KB |
Correct: 2356 out of 12000 queries used. |
4 |
Correct |
4 ms |
8540 KB |
Correct: 2683 out of 12000 queries used. |
5 |
Correct |
3 ms |
8540 KB |
Correct: 2042 out of 12000 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8536 KB |
Correct: 2108 out of 12000 queries used. |
2 |
Correct |
3 ms |
8536 KB |
Correct: 1994 out of 12000 queries used. |
3 |
Correct |
3 ms |
8640 KB |
Correct: 2356 out of 12000 queries used. |
4 |
Correct |
4 ms |
8540 KB |
Correct: 2683 out of 12000 queries used. |
5 |
Correct |
3 ms |
8540 KB |
Correct: 2042 out of 12000 queries used. |
6 |
Correct |
3 ms |
8536 KB |
Correct: 2550 out of 12000 queries used. |
7 |
Correct |
4 ms |
8540 KB |
Correct: 2977 out of 12000 queries used. |
8 |
Correct |
3 ms |
8540 KB |
Correct: 2039 out of 12000 queries used. |
9 |
Correct |
3 ms |
8540 KB |
Correct: 2017 out of 12000 queries used. |
10 |
Correct |
3 ms |
8540 KB |
Correct: 2330 out of 12000 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8536 KB |
Correct: 2254 out of 500000 queries used. |
2 |
Correct |
4 ms |
8792 KB |
Correct: 2680 out of 500000 queries used. |
3 |
Correct |
3 ms |
8564 KB |
Correct: 5222 out of 500000 queries used. |
4 |
Correct |
3 ms |
8540 KB |
Correct: 5680 out of 500000 queries used. |
5 |
Correct |
3 ms |
8540 KB |
Correct: 3414 out of 500000 queries used. |
6 |
Correct |
3 ms |
8540 KB |
Correct: 3040 out of 500000 queries used. |
7 |
Correct |
4 ms |
8540 KB |
Correct: 5817 out of 500000 queries used. |
8 |
Correct |
3 ms |
8540 KB |
Correct: 5981 out of 500000 queries used. |
9 |
Correct |
3 ms |
8540 KB |
Correct: 5791 out of 500000 queries used. |
10 |
Correct |
3 ms |
8540 KB |
Correct: 5451 out of 500000 queries used. |
11 |
Correct |
3 ms |
8536 KB |
Correct: 2108 out of 12000 queries used. |
12 |
Correct |
3 ms |
8536 KB |
Correct: 1994 out of 12000 queries used. |
13 |
Correct |
3 ms |
8640 KB |
Correct: 2356 out of 12000 queries used. |
14 |
Correct |
4 ms |
8540 KB |
Correct: 2683 out of 12000 queries used. |
15 |
Correct |
3 ms |
8540 KB |
Correct: 2042 out of 12000 queries used. |
16 |
Correct |
3 ms |
8536 KB |
Correct: 2550 out of 12000 queries used. |
17 |
Correct |
4 ms |
8540 KB |
Correct: 2977 out of 12000 queries used. |
18 |
Correct |
3 ms |
8540 KB |
Correct: 2039 out of 12000 queries used. |
19 |
Correct |
3 ms |
8540 KB |
Correct: 2017 out of 12000 queries used. |
20 |
Correct |
3 ms |
8540 KB |
Correct: 2330 out of 12000 queries used. |
21 |
Correct |
3 ms |
8536 KB |
Correct: 2244 out of 25000 queries used. |
22 |
Correct |
4 ms |
8540 KB |
Correct: 3836 out of 25000 queries used. |
23 |
Correct |
4 ms |
8540 KB |
Correct: 3726 out of 25000 queries used. |
24 |
Correct |
4 ms |
8540 KB |
Correct: 4281 out of 25000 queries used. |
25 |
Correct |
3 ms |
8540 KB |
Correct: 5496 out of 25000 queries used. |
26 |
Correct |
3 ms |
8540 KB |
Correct: 5083 out of 25000 queries used. |
27 |
Correct |
3 ms |
8540 KB |
Correct: 5110 out of 25000 queries used. |
28 |
Correct |
3 ms |
8540 KB |
Correct: 5675 out of 25000 queries used. |
29 |
Correct |
3 ms |
8540 KB |
Correct: 5369 out of 25000 queries used. |
30 |
Correct |
4 ms |
8520 KB |
Correct: 5756 out of 25000 queries used. |
31 |
Correct |
3 ms |
8540 KB |
Correct: 5753 out of 25000 queries used. |
32 |
Correct |
3 ms |
8540 KB |
Correct: 1987 out of 25000 queries used. |
33 |
Correct |
3 ms |
8536 KB |
Correct: 5909 out of 25000 queries used. |
34 |
Correct |
3 ms |
8536 KB |
Correct: 5709 out of 25000 queries used. |
35 |
Correct |
4 ms |
8540 KB |
Correct: 5923 out of 25000 queries used. |
36 |
Correct |
3 ms |
8540 KB |
Correct: 5895 out of 25000 queries used. |
37 |
Correct |
3 ms |
8536 KB |
Correct: 5748 out of 25000 queries used. |
38 |
Correct |
4 ms |
8540 KB |
Correct: 5860 out of 25000 queries used. |
39 |
Correct |
4 ms |
8536 KB |
Correct: 5791 out of 25000 queries used. |
40 |
Correct |
3 ms |
8540 KB |
Correct: 5845 out of 25000 queries used. |
41 |
Correct |
3 ms |
8540 KB |
Correct: 5912 out of 25000 queries used. |
42 |
Correct |
3 ms |
8540 KB |
Correct: 5835 out of 25000 queries used. |
43 |
Correct |
3 ms |
8540 KB |
Correct: 2196 out of 25000 queries used. |
44 |
Correct |
4 ms |
8540 KB |
Correct: 5744 out of 25000 queries used. |
45 |
Correct |
5 ms |
8468 KB |
Correct: 5803 out of 25000 queries used. |
46 |
Correct |
3 ms |
8540 KB |
Correct: 5739 out of 25000 queries used. |
47 |
Correct |
4 ms |
8540 KB |
Correct: 5713 out of 25000 queries used. |
48 |
Correct |
4 ms |
8792 KB |
Correct: 5827 out of 25000 queries used. |
49 |
Correct |
3 ms |
8540 KB |
Correct: 5723 out of 25000 queries used. |
50 |
Correct |
3 ms |
8540 KB |
Correct: 5749 out of 25000 queries used. |
51 |
Correct |
3 ms |
8540 KB |
Correct: 5809 out of 25000 queries used. |
52 |
Correct |
3 ms |
8540 KB |
Correct: 5864 out of 25000 queries used. |
53 |
Correct |
5 ms |
8540 KB |
Correct: 6274 out of 25000 queries used. |
54 |
Correct |
4 ms |
8540 KB |
Correct: 3200 out of 25000 queries used. |
55 |
Correct |
3 ms |
8540 KB |
Correct: 5824 out of 25000 queries used. |
56 |
Correct |
4 ms |
8540 KB |
Correct: 6127 out of 25000 queries used. |
57 |
Correct |
3 ms |
8536 KB |
Correct: 5892 out of 25000 queries used. |
58 |
Correct |
3 ms |
8792 KB |
Correct: 6205 out of 25000 queries used. |
59 |
Correct |
4 ms |
8792 KB |
Correct: 5750 out of 25000 queries used. |
60 |
Correct |
5 ms |
8540 KB |
Correct: 4200 out of 25000 queries used. |
61 |
Correct |
3 ms |
8536 KB |
Correct: 3988 out of 25000 queries used. |
62 |
Correct |
3 ms |
8536 KB |
Correct: 4711 out of 25000 queries used. |
63 |
Correct |
3 ms |
8540 KB |
Correct: 4260 out of 25000 queries used. |
64 |
Correct |
4 ms |
8540 KB |
Correct: 6647 out of 25000 queries used. |
65 |
Correct |
3 ms |
8536 KB |
Correct: 3411 out of 25000 queries used. |
66 |
Correct |
3 ms |
8540 KB |
Correct: 4645 out of 25000 queries used. |
67 |
Correct |
4 ms |
8540 KB |
Correct: 4091 out of 25000 queries used. |
68 |
Correct |
4 ms |
8540 KB |
Correct: 4202 out of 25000 queries used. |
69 |
Correct |
4 ms |
8540 KB |
Correct: 2942 out of 25000 queries used. |
70 |
Correct |
4 ms |
8540 KB |
Correct: 2105 out of 25000 queries used. |