#include "parks.h"
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
int fount2[200005], fount4[200005];
int sy2[200005], sy4[200005];
int numofvis;
vector<int> adj[200005];
map<int,int> emf;
bool visited[200005];
bool compare2(int a, int b){ return sy2[a] < sy2[b]; }
bool compare4(int a, int b){ return sy4[a] < sy4[b]; }
void dfs(int v){
visited[v] = true;
numofvis++;
int len = adj[v].size();
for(int i=0; i<len; i++){
int to = adj[v][i];
if(!visited[to]) dfs(to);
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
int n = x.size(), cnt2=0, cnt4=0;
for(int i=0; i<n; i++){
if(x[i] == 2){
fount2[cnt2] = i;
sy2[cnt2++] = y[i];
}
else{
fount4[cnt4] = i;
sy4[cnt4++] = y[i];
}
}
std::sort(&fount2[0],&fount2[cnt2],compare2);
std::sort(&sy2[0],&sy2[cnt2]);
std::sort(&fount4[0],&fount4[cnt4],compare4);
// for(int i=1; i<cnt4; i++) emf[sy4[fount4[i]]] = i;
// emf[sy4[fount4[0]]] = -1;
std::sort(&sy4[0],&sy4[cnt4]);
for(int i=1; i<cnt4; i++) emf[sy4[i]] = i;
emf[sy4[0]] = -1;
std::vector<int> u, v, a, b;
if(cnt2 == 0){
for(int i=0; i<cnt4-1; i++){
if(sy4[i+1]-sy4[i] != 2) return 0;
u.push_back(fount4[i]);
v.push_back(fount4[i+1]);
a.push_back(5);
b.push_back(sy4[i]+1);
}
build(u, v, a, b);
return 1;
}
if(cnt4 == 0){
for(int i=0; i<cnt2-1; i++){
if(sy2[i+1]-sy2[i] != 2) return 0;
u.push_back(fount2[i]);
v.push_back(fount2[i+1]);
a.push_back(1);
b.push_back(sy2[i]+1);
}
build(u, v, a, b);
return 1;
}
for(int i=0; i<cnt2; i++){
if(i == cnt2-1) continue;
while(sy2[i+1]-sy2[i] == 2){
u.push_back(fount2[i]);
v.push_back(fount2[i+1]);
a.push_back(1);
b.push_back(sy2[i]+1);
i++;
}
}
for(int i=0; i<cnt4; i++){
if(i == cnt4-1) continue;
while(sy4[i+1]-sy4[i] == 2){
u.push_back(fount4[i]);
v.push_back(fount4[i+1]);
a.push_back(5);
b.push_back(sy4[i]+1);
i++;
}
}
for(int i=0; i<cnt2; i++){
int temp = emf[sy2[i]];
if(temp == 0) continue;
if(temp == -1) temp = 0;
u.push_back(fount2[i]);
v.push_back(fount4[temp]);
a.push_back(3);
b.push_back(sy2[i]-1);
}
int s = u.size();
for(int i=0; i<s; i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(u[0]);
if(numofvis != n) return 0;
build(u, v, a, b);
return 1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4896 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
4 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
78 ms |
12144 KB |
Output is correct |
10 |
Correct |
10 ms |
5836 KB |
Output is correct |
11 |
Correct |
34 ms |
8856 KB |
Output is correct |
12 |
Correct |
12 ms |
6348 KB |
Output is correct |
13 |
Correct |
15 ms |
6748 KB |
Output is correct |
14 |
Correct |
4 ms |
4940 KB |
Output is correct |
15 |
Correct |
4 ms |
4940 KB |
Output is correct |
16 |
Correct |
78 ms |
12148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4896 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
4 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
78 ms |
12144 KB |
Output is correct |
10 |
Correct |
10 ms |
5836 KB |
Output is correct |
11 |
Correct |
34 ms |
8856 KB |
Output is correct |
12 |
Correct |
12 ms |
6348 KB |
Output is correct |
13 |
Correct |
15 ms |
6748 KB |
Output is correct |
14 |
Correct |
4 ms |
4940 KB |
Output is correct |
15 |
Correct |
4 ms |
4940 KB |
Output is correct |
16 |
Correct |
78 ms |
12148 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Incorrect |
3 ms |
4956 KB |
Pair u[2]=2 @(2, 4) and v[2]=3 @(4, 6) does not form a valid edge (distance != 2) |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4896 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
4 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
78 ms |
12144 KB |
Output is correct |
10 |
Correct |
10 ms |
5836 KB |
Output is correct |
11 |
Correct |
34 ms |
8856 KB |
Output is correct |
12 |
Correct |
12 ms |
6348 KB |
Output is correct |
13 |
Correct |
15 ms |
6748 KB |
Output is correct |
14 |
Correct |
4 ms |
4940 KB |
Output is correct |
15 |
Correct |
4 ms |
4940 KB |
Output is correct |
16 |
Correct |
78 ms |
12148 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Incorrect |
3 ms |
4956 KB |
Pair u[2]=2 @(2, 4) and v[2]=3 @(4, 6) does not form a valid edge (distance != 2) |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4896 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
4 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
78 ms |
12144 KB |
Output is correct |
10 |
Correct |
10 ms |
5836 KB |
Output is correct |
11 |
Correct |
34 ms |
8856 KB |
Output is correct |
12 |
Correct |
12 ms |
6348 KB |
Output is correct |
13 |
Correct |
15 ms |
6748 KB |
Output is correct |
14 |
Correct |
4 ms |
4940 KB |
Output is correct |
15 |
Correct |
4 ms |
4940 KB |
Output is correct |
16 |
Correct |
78 ms |
12148 KB |
Output is correct |
17 |
Incorrect |
3 ms |
4940 KB |
Solution announced impossible, but it is possible. |
18 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4896 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
4 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
78 ms |
12144 KB |
Output is correct |
10 |
Correct |
10 ms |
5836 KB |
Output is correct |
11 |
Correct |
34 ms |
8856 KB |
Output is correct |
12 |
Correct |
12 ms |
6348 KB |
Output is correct |
13 |
Correct |
15 ms |
6748 KB |
Output is correct |
14 |
Correct |
4 ms |
4940 KB |
Output is correct |
15 |
Correct |
4 ms |
4940 KB |
Output is correct |
16 |
Correct |
78 ms |
12148 KB |
Output is correct |
17 |
Incorrect |
130 ms |
22480 KB |
Solution announced impossible, but it is possible. |
18 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4896 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
4 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
78 ms |
12144 KB |
Output is correct |
10 |
Correct |
10 ms |
5836 KB |
Output is correct |
11 |
Correct |
34 ms |
8856 KB |
Output is correct |
12 |
Correct |
12 ms |
6348 KB |
Output is correct |
13 |
Correct |
15 ms |
6748 KB |
Output is correct |
14 |
Correct |
4 ms |
4940 KB |
Output is correct |
15 |
Correct |
4 ms |
4940 KB |
Output is correct |
16 |
Correct |
78 ms |
12148 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Incorrect |
3 ms |
4956 KB |
Pair u[2]=2 @(2, 4) and v[2]=3 @(4, 6) does not form a valid edge (distance != 2) |
19 |
Halted |
0 ms |
0 KB |
- |