| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 602395 | rrrr10000 | Keys (IOI21_keys) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<P> vp;
typedef vector<vp> vvp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define fi first
#define se second
#define pb emplace_back
#define all(a) a.begin(),a.end()
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
vi dx={2,0,-2,0},dy={0,2,0,-2};
ll mx=200005;
int construct_roads(std::vector<int> X, std::vector<int> Y) {
if (X.size() == 1) {
build({}, {}, {}, {});
return 1;
}
ll n=X.size();
map<P,ll> mp;
rep(i,n)mp[P(X[i],Y[i])]=i;
vp edge;
rep(i,n)rep(j,2){
ll nx=X[i]+dx[j],ny=Y[i]+dy[j];
if(mp.count(P(nx,ny)))edge.pb(i,mp[P(nx,ny)]);
}
{
vvi g(n);
for(auto x:edge){
g[x.fi].pb(x.se);
g[x.se].pb(x.fi);
}
queue<ll> que;
vb done(n,false);
done[0]=true;
que.push(0);
while(!que.empty()){
ll t=que.front();que.pop();
for(ll x:g[t])if(!done[x]){
done[x]=true;que.push(x);
}
}
rep(i,n)if(!done[i])return 0;
}
for(auto &x:edge)if(x.fi>x.se)swap(x.fi,x.se);
sort(all(edge));
vb use(edge.size(),true);
vp e;
vi ddx={2,0,2},ddy={0,2,2};
rep(i,n){
vi al;
al.pb(i);
rep(j,3)if(mp.count(P(X[i]+ddx[j],Y[i]+ddy[j])))al.pb(mp[P(X[i]+ddx[j],Y[i]+ddy[j])]);
if(al.size()<=3){
rep(j,3)rep(k,j)if(abs(X[al[j]]-X[al[k]])+abs(Y[al[j]]-Y[al[k]])==2)e.pb(al[j],al[k]);
}
else{
vp t1={P(0,1),P(0,2),P(1,3)},t2={P(0,1),P(1,3),P(2,3)};
if((X[i]+Y[i]+2)%4==2)use[lb(edge,P(min(al[2],al[3]),max(al[2],al[3])))]=false;
else use[lb(edge,P(min(al[0],al[2]),max(al[0],al[2])))]=false;
}
}
vector<int> u, v, a, b;
rep(i,edge.size())if(use[i]){
P x=edge[i];
u.pb(x.fi);v.pb(x.se);
P p((X[x.fi]+X[x.se])/2,(Y[x.fi]+Y[x.se])/2);
if(X[x.fi]==X[x.se]){
p.fi++;
if((p.fi+p.se)%4==2)p.fi-=2;
}
else{
p.se++;
if((p.fi+p.se)%4==0)p.se-=2;
}
a.pb(p.fi);b.pb(p.se);
}
build(u,v,a,b);
return 1;
}