// #include <iostream>
// #include <vector>
// using namespace std;
// // #include "parks.h"
// #include <cstdio>
// #include <cmath>
// #include <cassert>
// #include <vector>
// #include <string>
// using namespace std;
// static void check(bool cond, string message) {
// if (!cond) {
// printf("%s\n", message.c_str());
// fclose(stdout);
// exit(0);
// }
// }
// static int n;
// static bool build_called;
// static int m;
// static vector<int> _u, _v, _a, _b;
// void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) {
// check(!build_called, "build is called more than once");
// build_called = true;
// m = u.size();
// check(int(v.size()) == m, "u.size() != v.size()");
// check(int(a.size()) == m, "u.size() != a.size()");
// check(int(b.size()) == m, "u.size() != b.size()");
// check(m <= 2*n, "Construction too large"); // Vertex degrees are at most 4
// _u = u;
// _v = v;
// _a = a;
// _b = b;
// }
// const int N = 200000 + 10;
// int seen[10][N];
// int seen2[10][N];
// int used[12][N];
// int sn = 0;
// vector<pair<int,int>> d = {{0,2},{2,0},{-2,0},{0,-2}};
// vector<int> a,b,X,Y;
// vector<pair<int,int>> up,nup;
// void dfs(int i,int j){
// seen2[i][j] = true;
// sn++;
// for (auto [x,y] : d){
// int ni = i + x;
// int nj = j + y;
// if (!seen[ni][nj] or seen2[ni][nj])
// continue;
// if (i==ni)
// up.push_back({seen[i][j]-1,seen[ni][nj]-1});
// else
// nup.push_back({seen[i][j]-1,seen[ni][nj]-1});
// dfs(ni,nj);
// }
// }
// pair<int,int> det(int x1,int y1,int x2,int y2){
// if (x1 == x2){
// if (y1>y2)
// swap(y1,y2);
// if (x1 == 2)
// return {1,y1+1};
// if (x1 == 6)
// return {7,y1+1};
// if (used[3][y1-1] or used[3][y2 + 1])
// return {5,y1 + 1};
// return {3,y1 + 1};
// }
// if (x1>x2)
// swap(x1,x2);
// if (used[x1+1][y1-1])
// return {x1+1,y1+1};
// return {x1+1,y1-1};
// }
// int construct_roads(vector<int> x,vector<int> y){
// int n = x.size();
// int mny = 1e7,k;
// for (int i=0;i<n;i++){
// seen[x[i]][y[i]] = i+1;
// if (y[i]<mny)
// mny = y[i],k = x[i];
// }
// dfs(k,mny);
// if (sn!=n)
// return 0;
// for (auto [i,j] : up){
// auto [ii,jj] = det(x[i],y[i],x[j],y[j]);
// used[ii][jj] = true;
// a.push_back(i);
// b.push_back(j);
// X.push_back(ii);
// Y.push_back(jj);
// }
// for (auto [i,j] : nup){
// auto [ii,jj] = det(x[i],y[i],x[j],y[j]);
// used[ii][jj] = true;
// a.push_back(i);
// b.push_back(j);
// X.push_back(ii);
// Y.push_back(jj);
// }
// build(a,b,X,Y);
// return 1;
// }
// int main() {
// assert(scanf("%d", &n) == 1);
// vector<int> x(n), y(n);
// for (int i = 0; i < n; i++) {
// assert(scanf("%d%d", &x[i], &y[i]) == 2);
// }
// fclose(stdin);
// build_called = false;
// const int possible = construct_roads(x, y);
// check(possible == 0 || possible == 1, "Invalid return value of construct_roads()");
// if (possible == 1) {
// check(build_called, "construct_roads() returned 1 without calling build()");
// } else {
// check(!build_called, "construct_roads() called build() but returned 0");
// }
// printf("OK\n");
// printf("%d\n", possible);
// if (possible == 1) {
// printf("%d\n", m);
// for (int j = 0; j < m; j++) {
// printf("%d %d %d %d\n", _u[j], _v[j], _a[j], _b[j]);
// }
// }
// fclose(stdout);
// return 0;
// }
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#include "parks.h"
#include <cstdio>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
const int N = 200000 + 10;
int seen[10][N];
int seen2[10][N];
int used[12][N];
int sn = 0;
vector<pair<int,int>> d = {{0,2},{2,0},{-2,0},{0,-2}};
vector<int> a,b,X,Y;
vector<pair<int,int>> up,nup;
void dfs(int i,int j){
seen2[i][j] = true;
sn++;
for (auto [x,y] : d){
int ni = i + x;
int nj = j + y;
if (!seen[ni][nj] or seen2[ni][nj])
continue;
if (i==ni and i==4)
up.push_back({seen[i][j]-1,seen[ni][nj]-1});
else
nup.push_back({seen[i][j]-1,seen[ni][nj]-1});
dfs(ni,nj);
}
}
void dfs2(int i,int j){
if (seen2[i][j])
return;
seen2[i][j] = true;
sn++;
int ni = i;
int nj = j + 2;
if (!seen[ni][nj] or seen2[ni][nj])
return;
nup.push_back({seen[i][j]-1,seen[ni][nj]-1});
dfs2(ni,nj);
}
pair<int,int> det(int x1,int y1,int x2,int y2){
if (x1 == x2){
if (y1>y2)
swap(y1,y2);
if (x1 == 2)
return {1,y1+1};
if (x1 == 6)
return {7,y1+1};
if (used[3][y1-1] or used[3][y2 + 1])
return {5,y1 + 1};
return {3,y1 + 1};
}
if (x1>x2)
swap(x1,x2);
if (used[x1+1][y1-1])
return {x1+1,y1+1};
return {x1+1,y1-1};
}
int construct_roads(vector<int> x,vector<int> y){
int n = x.size();
int mny = 1e7,k;
for (int i=0;i<n;i++){
if (x[i]==2 or x[i]==6)
dfs2(x[i],y[i]);
}
for (int i=0;i<n;i++){
if (!seen2[x[i]][y[i]])
dfs(x[i],y[i]);
}
if (sn!=n)
return 0;
sort(begin(up),end(up));
for (auto [i,j] : up){
auto [ii,jj] = det(x[i],y[i],x[j],y[j]);
used[ii][jj] = true;
a.push_back(i);
b.push_back(j);
X.push_back(ii);
Y.push_back(jj);
}
for (auto [i,j] : nup){
auto [ii,jj] = det(x[i],y[i],x[j],y[j]);
used[ii][jj] = true;
a.push_back(i);
b.push_back(j);
X.push_back(ii);
Y.push_back(jj);
}
build(a,b,X,Y);
return 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:277:6: warning: unused variable 'mny' [-Wunused-variable]
277 | int mny = 1e7,k;
| ^~~
parks.cpp:277:16: warning: unused variable 'k' [-Wunused-variable]
277 | int mny = 1e7,k;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
