Submission #435331

#	Time	Username	Problem	Language	Result	Execution time	Memory
435331		jangwonyoung	분수 공원 (IOI21_parks)	C++17	100 / 100	2982 ms	123008 KiB

parks

/////////////////////////////
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
#define n nnn
typedef array<int,4> arin;
const int N=2e5+1;
int n;
int cx[N],cy[N];
vector<arin>edges;
vector<int>built[4];
int dx[4]={-2,0,2,0};
int dy[4]={0,-2,0,2};
int ex[4]={-1,1,1,-1};
int ey[4]={-1,-1,1,1};
int p[N];
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
bool join(int x,int y){
    x=find(x);y=find(y);
    if(x==y) return false;
    p[x]=y;
    return true;
}
map<pair<int,int>,int>mp,sq;
map<pair<int,int>,bool>used;
map<pair<int,int>,bool>ban;
vector<pair<int,pair<int,int> > >adj[N];
bool vis[N];

#define fi first
#define se second
void dfs(int id){
    for(auto c:adj[id]){
        if(!vis[c.fi]){
            vis[c.fi]=true;
            ban[c.se]=true;
            dfs(c.fi);
        }
    }
}
vector<pair<pair<int,int>,int> >sqq;
int construct_roads(vector<int>x,vector<int>y){
    n=x.size();
    for(int i=1; i<=n ;i++){
        cx[i]=x[i-1];
        cy[i]=y[i-1];
        mp[{cx[i],cy[i]}]=i;
        p[i]=i;
    }
    int m=0;
    for(int i=1; i<=n ;i++){
        if(!mp[{cx[i],cy[i]}]) continue;
        if(!mp[{cx[i]+2,cy[i]}]) continue;
        if(!mp[{cx[i],cy[i]+2}]) continue;
        if(!mp[{cx[i]+2,cy[i]+2}]) continue;
        sq[{cx[i]+1,cy[i]+1}]=++m;
    }
	typedef pair<int,int> pii;
	for(auto c:sq) sqq.push_back({c.fi,c.se});
    for(auto c:sqq){
        auto cur=c.fi;
		int c1=mp[(pii){cur.fi-1,cur.se-1}];
		int c2=mp[(pii){cur.fi+1,cur.se-1}];
		int c3=mp[(pii){cur.fi-1,cur.se+1}];
		int c4=mp[(pii){cur.fi+1,cur.se+1}];
        if((cur.fi+cur.se)%4==0){//horizontal
            int u=sq[{cur.fi-2,cur.se}];
            int v=sq[{cur.fi+2,cur.se}];
            adj[u].push_back({c.se,{c1,c3}});
            adj[v].push_back({c.se,{c2,c4}});
        }
        else{
            int u=sq[{cur.fi,cur.se-2}];
            int v=sq[{cur.fi,cur.se+2}];
            adj[u].push_back({c.se,{c1,c2}});
            adj[v].push_back({c.se,{c3,c4}});
        }
    }
    dfs(0);
    for(int i=1; i<=n ;i++){
        if((cx[i]+cy[i])%4!=0) continue;
        for(int j=0; j<4 ;j++){
            int s=mp[{cx[i]+dx[j],cy[i]+dy[j]}];
            if(s==0) continue;
            if(ban[{i,s}]==1 || ban[{s,i}]==1) continue;
            if(join(i,s)){
                edges.push_back(arin{i-1,s-1,cx[i]+ex[j],cy[i]+ey[j]});
            }
        }
    }
    if(edges.size()!=n-1) return 0;
    for(auto c:edges){
        for(int j=0; j<4 ;j++){
            built[j].push_back(c[j]);
        }
    }
    build(built[0],built[1],built[2],built[3]);
	return 1;
}
////////////////////////////////////////////////////////////////////////

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:94:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |     if(edges.size()!=n-1) return 0;
      |        ~~~~~~~~~~~~^~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30