#include "parks.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define fr first
#define sc second
const int N=2e5+5;
vector<array<int,3>> g[N];
int p[N];
vector<int> sz(N,1);
int f(int x){
if(p[x]==x) return x;
return p[x]=f(p[x]);
}
bool add(int a, int b){
a=f(a);
b=f(b);
if(a==b) return 0;
if(rand()%2) swap(a,b);//<-может лагать
p[a]=b;
sz[b]+=sz[a];
return 1;
}
void add_edge(int a, int b, int u, int v){
g[a].pb({b,u,v});
g[b].pb({a,u,v});
}
int construct_roads(vector<int> x, vector<int> y) {
int n=x.size();
map<pair<int,int>,int> X,Y;
for(int i=0;i<n;i++){
p[i]=i;
X[{x[i],y[i]}]=i;
}
vector<int> u,v,a,b;
for(int i=0;i<n;i++){
if(X.count({x[i]-2,y[i]})){
int j=X[{x[i]-2,y[i]}];
if(add(i,j)){
u.pb(i);v.pb(j);
a.pb(-1);b.pb(-1);
int A=u.size()-1;
if(Y.count({x[i]-1,y[i]-1})){
int B=Y[{x[i]-1,y[i]-1}];
add_edge(A,B,x[i]-1,y[i]-1);
Y.erase({x[i]-1,y[i]-1});
}
else{
Y[{x[i]-1,y[i]-1}]=A;
}
if(Y.count({x[i]-1,y[i]+1})){
int B=Y[{x[i]-1,y[i]+1}];
add_edge(A,B,x[i]-1,y[i]+1);
Y.erase({x[i]-1,y[i]+1});
}
else{
Y[{x[i]-1,y[i]+1}]=A;
}
}
}
if(X.count({x[i],y[i]-2})){
int j=X[{x[i],y[i]-2}];
if(add(i,j)){
u.pb(i);v.pb(j);
a.pb(-1);b.pb(-1);
int A=u.size()-1;
if(Y.count({x[i]-1,y[i]-1})){
int B=Y[{x[i]-1,y[i]-1}];
add_edge(A,B,x[i]-1,y[i]-1);
Y.erase({x[i]-1,y[i]-1});
}
else{
Y[{x[i]-1,y[i]-1}]=A;
}
if(Y.count({x[i]+1,y[i]-1})){
int B=Y[{x[i]+1,y[i]-1}];
add_edge(A,B,x[i]+1,y[i]-1);
Y.erase({x[i]+1,y[i]-1});
}
else{
Y[{x[i]+1,y[i]+1}]=A;
}
}
}
}
if(sz[f(0)]<n) return 0;
int m=u.size();
vector<int> used(m);
function<void(int)> dfs=[&](int x){
used[x]=1;
for(auto [it,A,B]:g[x]){
if(used[it]) continue;
a[it]=A;
b[it]=B;
dfs(it);
}
};
for(auto [it,A]: Y){
if(used[A]) continue;
a[A]=it.fr;
b[A]=it.sc;
dfs(A);
}
for(int i=0;i<m;i++){
if(used[i]) continue;
a[i]=g[i].back()[1];
b[i]=g[i].back()[2];
g[i].pop_back();
dfs(i);
}
build(u,v,a,b);
return 1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5716 KB |
Output is correct |
2 |
Correct |
3 ms |
5716 KB |
Output is correct |
3 |
Correct |
3 ms |
5716 KB |
Output is correct |
4 |
Correct |
3 ms |
5736 KB |
Output is correct |
5 |
Correct |
3 ms |
5800 KB |
Output is correct |
6 |
Correct |
3 ms |
5808 KB |
Output is correct |
7 |
Correct |
4 ms |
5804 KB |
Output is correct |
8 |
Correct |
4 ms |
5804 KB |
Output is correct |
9 |
Correct |
307 ms |
30092 KB |
Output is correct |
10 |
Correct |
13 ms |
8372 KB |
Output is correct |
11 |
Correct |
69 ms |
18740 KB |
Output is correct |
12 |
Correct |
19 ms |
9604 KB |
Output is correct |
13 |
Correct |
51 ms |
14804 KB |
Output is correct |
14 |
Correct |
3 ms |
5972 KB |
Output is correct |
15 |
Correct |
5 ms |
6100 KB |
Output is correct |
16 |
Correct |
237 ms |
30160 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5716 KB |
Output is correct |
2 |
Correct |
3 ms |
5716 KB |
Output is correct |
3 |
Correct |
3 ms |
5716 KB |
Output is correct |
4 |
Correct |
3 ms |
5736 KB |
Output is correct |
5 |
Correct |
3 ms |
5800 KB |
Output is correct |
6 |
Correct |
3 ms |
5808 KB |
Output is correct |
7 |
Correct |
4 ms |
5804 KB |
Output is correct |
8 |
Correct |
4 ms |
5804 KB |
Output is correct |
9 |
Correct |
307 ms |
30092 KB |
Output is correct |
10 |
Correct |
13 ms |
8372 KB |
Output is correct |
11 |
Correct |
69 ms |
18740 KB |
Output is correct |
12 |
Correct |
19 ms |
9604 KB |
Output is correct |
13 |
Correct |
51 ms |
14804 KB |
Output is correct |
14 |
Correct |
3 ms |
5972 KB |
Output is correct |
15 |
Correct |
5 ms |
6100 KB |
Output is correct |
16 |
Correct |
237 ms |
30160 KB |
Output is correct |
17 |
Incorrect |
3 ms |
5716 KB |
Tree (a[1], b[1]) = (5, 5) is not adjacent to edge between u[1]=0 @(4, 4) and v[1]=2 @(4, 2) |
18 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5716 KB |
Output is correct |
2 |
Correct |
3 ms |
5716 KB |
Output is correct |
3 |
Correct |
3 ms |
5716 KB |
Output is correct |
4 |
Correct |
3 ms |
5736 KB |
Output is correct |
5 |
Correct |
3 ms |
5800 KB |
Output is correct |
6 |
Correct |
3 ms |
5808 KB |
Output is correct |
7 |
Correct |
4 ms |
5804 KB |
Output is correct |
8 |
Correct |
4 ms |
5804 KB |
Output is correct |
9 |
Correct |
307 ms |
30092 KB |
Output is correct |
10 |
Correct |
13 ms |
8372 KB |
Output is correct |
11 |
Correct |
69 ms |
18740 KB |
Output is correct |
12 |
Correct |
19 ms |
9604 KB |
Output is correct |
13 |
Correct |
51 ms |
14804 KB |
Output is correct |
14 |
Correct |
3 ms |
5972 KB |
Output is correct |
15 |
Correct |
5 ms |
6100 KB |
Output is correct |
16 |
Correct |
237 ms |
30160 KB |
Output is correct |
17 |
Incorrect |
3 ms |
5716 KB |
Tree (a[1], b[1]) = (5, 5) is not adjacent to edge between u[1]=0 @(4, 4) and v[1]=2 @(4, 2) |
18 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5716 KB |
Output is correct |
2 |
Correct |
3 ms |
5716 KB |
Output is correct |
3 |
Correct |
3 ms |
5716 KB |
Output is correct |
4 |
Correct |
3 ms |
5736 KB |
Output is correct |
5 |
Correct |
3 ms |
5800 KB |
Output is correct |
6 |
Correct |
3 ms |
5808 KB |
Output is correct |
7 |
Correct |
4 ms |
5804 KB |
Output is correct |
8 |
Correct |
4 ms |
5804 KB |
Output is correct |
9 |
Correct |
307 ms |
30092 KB |
Output is correct |
10 |
Correct |
13 ms |
8372 KB |
Output is correct |
11 |
Correct |
69 ms |
18740 KB |
Output is correct |
12 |
Correct |
19 ms |
9604 KB |
Output is correct |
13 |
Correct |
51 ms |
14804 KB |
Output is correct |
14 |
Correct |
3 ms |
5972 KB |
Output is correct |
15 |
Correct |
5 ms |
6100 KB |
Output is correct |
16 |
Correct |
237 ms |
30160 KB |
Output is correct |
17 |
Correct |
3 ms |
5716 KB |
Output is correct |
18 |
Correct |
3 ms |
5796 KB |
Output is correct |
19 |
Correct |
3 ms |
5716 KB |
Output is correct |
20 |
Correct |
578 ms |
47376 KB |
Output is correct |
21 |
Incorrect |
697 ms |
45636 KB |
Tree (a[0], b[0]) = (56859, 56865) is not adjacent to edge between u[0]=0 @(56858, 56864) and v[0]=178618 @(56858, 56862) |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5716 KB |
Output is correct |
2 |
Correct |
3 ms |
5716 KB |
Output is correct |
3 |
Correct |
3 ms |
5716 KB |
Output is correct |
4 |
Correct |
3 ms |
5736 KB |
Output is correct |
5 |
Correct |
3 ms |
5800 KB |
Output is correct |
6 |
Correct |
3 ms |
5808 KB |
Output is correct |
7 |
Correct |
4 ms |
5804 KB |
Output is correct |
8 |
Correct |
4 ms |
5804 KB |
Output is correct |
9 |
Correct |
307 ms |
30092 KB |
Output is correct |
10 |
Correct |
13 ms |
8372 KB |
Output is correct |
11 |
Correct |
69 ms |
18740 KB |
Output is correct |
12 |
Correct |
19 ms |
9604 KB |
Output is correct |
13 |
Correct |
51 ms |
14804 KB |
Output is correct |
14 |
Correct |
3 ms |
5972 KB |
Output is correct |
15 |
Correct |
5 ms |
6100 KB |
Output is correct |
16 |
Correct |
237 ms |
30160 KB |
Output is correct |
17 |
Correct |
690 ms |
57228 KB |
Output is correct |
18 |
Incorrect |
674 ms |
57268 KB |
Tree (a[40134], b[40134]) = (50003, 50005) is not adjacent to edge between u[40134]=40135 @(50002, 50004) and v[40134]=183490 @(50002, 50002) |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5716 KB |
Output is correct |
2 |
Correct |
3 ms |
5716 KB |
Output is correct |
3 |
Correct |
3 ms |
5716 KB |
Output is correct |
4 |
Correct |
3 ms |
5736 KB |
Output is correct |
5 |
Correct |
3 ms |
5800 KB |
Output is correct |
6 |
Correct |
3 ms |
5808 KB |
Output is correct |
7 |
Correct |
4 ms |
5804 KB |
Output is correct |
8 |
Correct |
4 ms |
5804 KB |
Output is correct |
9 |
Correct |
307 ms |
30092 KB |
Output is correct |
10 |
Correct |
13 ms |
8372 KB |
Output is correct |
11 |
Correct |
69 ms |
18740 KB |
Output is correct |
12 |
Correct |
19 ms |
9604 KB |
Output is correct |
13 |
Correct |
51 ms |
14804 KB |
Output is correct |
14 |
Correct |
3 ms |
5972 KB |
Output is correct |
15 |
Correct |
5 ms |
6100 KB |
Output is correct |
16 |
Correct |
237 ms |
30160 KB |
Output is correct |
17 |
Incorrect |
3 ms |
5716 KB |
Tree (a[1], b[1]) = (5, 5) is not adjacent to edge between u[1]=0 @(4, 4) and v[1]=2 @(4, 2) |
18 |
Halted |
0 ms |
0 KB |
- |