#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
map<P,int> pt; //점->인덱스
map<P,int> ed; //인덱스쌍->간선인덱스
set<P> vis;
vector<P> edge;
vector<int> adj[400000];
map<P,P> mp;
bool chk[400000];
P ret[400000];
int construct_roads(vector<int> x, vector<int> y) {
int n=x.size();
for(int i=0;i<n;i++) {
pt[P(x[i],y[i])]=i;
}
int m=0;
for(int i=0;i<n;i++) {
if (pt.find(P(x[i]-2,y[i]))!=pt.end()) {
int ind=pt[P(x[i]-2,y[i])];
if (ed.find(P(ind,i))!=ed.end()) {
ed[P(i,ind)]=ed[P(ind,i)];
}
else {
ed[P(i,ind)]=m++;
edge.push_back(P(i,ind));
}
}
if (pt.find(P(x[i]+2,y[i]))!=pt.end()) {
int ind=pt[P(x[i]+2,y[i])];
if (ed.find(P(ind,i))!=ed.end()) {
ed[P(i,ind)]=ed[P(ind,i)];
}
else {
ed[P(i,ind)]=m++;
edge.push_back(P(i,ind));
}
}
if (pt.find(P(x[i],y[i]-2))!=pt.end()) {
int ind=pt[P(x[i],y[i]-2)];
if (ed.find(P(ind,i))!=ed.end()) {
ed[P(i,ind)]=ed[P(ind,i)];
}
else {
ed[P(i,ind)]=m++;
edge.push_back(P(i,ind));
}
}
if (pt.find(P(x[i],y[i]+2))!=pt.end()) {
int ind=pt[P(x[i],y[i]+2)];
if (ed.find(P(ind,i))!=ed.end()) {
ed[P(i,ind)]=ed[P(ind,i)];
}
else {
ed[P(i,ind)]=m++;
edge.push_back(P(i,ind));
}
}
}
for(int i=0;i<edge.size();i++) {
if (x[edge[i].first]==x[edge[i].second]) {
int nx=x[edge[i].first]-1;
int ny=(y[edge[i].first]+y[edge[i].second])/2;
if (vis.find(P(nx,ny))==vis.end()) {
if (pt.find(P(nx-1,ny+1))!=pt.end()) {
int pind=pt[P(nx-1,ny+1)];
int eind=ed[P(pind,pt[P(nx+1,ny+1)])];
adj[eind].push_back(i);
adj[i].push_back(eind);
mp[P(i,eind)]=P(nx,ny);
mp[P(eind,i)]=P(nx,ny);
}
else if (pt.find(P(nx-1,ny-1))!=pt.end()) {
int pind=pt[P(nx-1,ny-1)];
int eind=ed[P(pind,pt[P(nx+1,ny-1)])];
adj[eind].push_back(i);
adj[i].push_back(eind);
mp[P(i,eind)]=P(nx,ny);
mp[P(eind,i)]=P(nx,ny);
}
else {
adj[i].push_back(i);
mp[P(i,i)]=P(nx,ny);
}
vis.insert(P(nx,ny));
}
nx=x[edge[i].first]+1;
if (vis.find(P(nx,ny))==vis.end()) {
if (pt.find(P(nx+1,ny+1))!=pt.end()) {
int pind=pt[P(nx+1,ny+1)];
int eind=ed[P(pind,pt[P(nx-1,ny+1)])];
adj[eind].push_back(i);
adj[i].push_back(eind);
mp[P(i,eind)]=P(nx,ny);
mp[P(eind,i)]=P(nx,ny);
}
else if (pt.find(P(nx+1,ny-1))!=pt.end()) {
int pind=pt[P(nx+1,ny-1)];
int eind=ed[P(pind,pt[P(nx-1,ny-1)])];
adj[eind].push_back(i);
adj[i].push_back(eind);
mp[P(i,eind)]=P(nx,ny);
mp[P(eind,i)]=P(nx,ny);
}
else {
adj[i].push_back(i);
mp[P(i,i)]=P(nx,ny);
}
vis.insert(P(nx,ny));
}
}
else {
int nx=(x[edge[i].first]+x[edge[i].second])/2;
int ny=y[edge[i].first]-1;
if (vis.find(P(nx,ny))==vis.end()) {
if (pt.find(P(nx-1,ny-1))!=pt.end()) {
int pind=pt[P(nx-1,ny-1)];
int eind=ed[P(pind,pt[P(nx-1,ny+1)])];
adj[eind].push_back(i);
adj[i].push_back(eind);
mp[P(i,eind)]=P(nx,ny);
mp[P(eind,i)]=P(nx,ny);
}
else if (pt.find(P(nx+1,ny-1))!=pt.end()) {
int pind=pt[P(nx+1,ny-1)];
int eind=ed[P(pind,pt[P(nx+1,ny+1)])];
adj[eind].push_back(i);
adj[i].push_back(eind);
mp[P(i,eind)]=P(nx,ny);
mp[P(eind,i)]=P(nx,ny);
}
else {
adj[i].push_back(i);
mp[P(i,i)]=P(nx,ny);
}
vis.insert(P(nx,ny));
}
ny=y[edge[i].first]+1;
if (vis.find(P(nx,ny))==vis.end()) {
if (pt.find(P(nx-1,ny+1))!=pt.end()) {
int pind=pt[P(nx-1,ny+1)];
int eind=ed[P(pind,pt[P(nx-1,ny-1)])];
adj[eind].push_back(i);
adj[i].push_back(eind);
mp[P(i,eind)]=P(nx,ny);
mp[P(eind,i)]=P(nx,ny);
}
else if (pt.find(P(nx+1,ny+1))!=pt.end()) {
int pind=pt[P(nx+1,ny+1)];
int eind=ed[P(pind,pt[P(nx+1,ny-1)])];
adj[eind].push_back(i);
adj[i].push_back(eind);
mp[P(i,eind)]=P(nx,ny);
mp[P(eind,i)]=P(nx,ny);
}
else {
adj[i].push_back(i);
mp[P(i,i)]=P(nx,ny);
}
vis.insert(P(nx,ny));
}
}
}
for(int i=0;i<m;i++) {
printf("%d\n",adj[i].size());
for(int j=0;j<adj[i].size();j++) {
printf("%d ",adj[i][j]);
}
printf("\n");
}
for(int i=0;i<m;i++) {
if (chk[i]) {
continue;
}
if (adj[i][0]==i||adj[i][1]==i) {
}
else {
continue;
}
ret[i]=mp[P(i,i)];
int now;
if (adj[i][0]==i) {
now=adj[i][1];
}
else {
now=adj[i][0];
}
int prev=i;
while (1) {
chk[now]=true;
if (adj[now][0]==now||adj[now][1]==now) {
ret[now]=mp[P(now,now)];
break;
}
if (adj[now][0]==prev) {
ret[now]=mp[P(now,adj[now][1])];
prev=now;
now=adj[now][1];
}
else {
ret[now]=mp[P(now,adj[now][0])];
prev=now;
now=adj[now][0];
}
}
}
for(int i=0;i<m;i++) {
if (chk[i]) {
continue;
}
ret[i]=mp[P(i,adj[i][0])];
int prev=i;
int now=adj[i][0];
chk[i]=true;
while (now!=i) {
chk[now]=true;
if (adj[now][0]==prev) {
ret[now]=mp[P(now,adj[now][1])];
prev=now;
now=adj[now][1];
}
else {
ret[now]=mp[P(now,adj[now][0])];
prev=now;
now=adj[now][0];
}
}
}
vector<int> uu;
vector<int> vv;
vector<int> aa;
vector<int> bb;
for(int i=0;i<m;i++) {
uu.push_back(edge[i].first);
vv.push_back(edge[i].second);
aa.push_back(ret[i].first);
bb.push_back(ret[i].second);
}
build(uu,vv,aa,bb);
return 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i=0;i<edge.size();i++) {
| ~^~~~~~~~~~~~
parks.cpp:168:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
168 | printf("%d\n",adj[i].size());
| ~^ ~~~~~~~~~~~~~
| | |
| int std::vector<int>::size_type {aka long unsigned int}
| %ld
parks.cpp:169:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | for(int j=0;j<adj[i].size();j++) {
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9676 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
9676 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9676 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
9676 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9676 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
9676 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9676 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
9676 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9676 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
9676 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9676 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
9676 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
