| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 894817 | Sir_Ahmed_Imran | 분수 공원 (IOI21_parks) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
///~~~LOTA~~~///
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define N 200001
int siz[N];
int par[N];
int root(int v){
if(!par[v]) return v;
par[v]=root(par[v]);
return par[v];
}
void merge(int v,int u){
v=root(v);
u=root(u);
par[u]=v;
siz[v]+=siz[u];
}
bool same(int v,int u){
return (root(v)==root(u));
}
int construct_roads(vector<int> x,vector<int> y){
map<pii,int> c,z;
int n,m,o,p,q,r;
n=x.size();
vector<int> v,u,w,a,b;
for(int i=0;i<n;i++){
w.append({{x[i],y[i]},i+1});
z[{x[i],y[i]}]=i+1;
siz[i+1]=1;
}
sort(all(w));
for(auto& i:w){
p=i.ff.ff;
q=i.ff.ss;
r=z[{p-2,q}];
if(r){
if(!same(i.ss,r)){
merge(i.ss,r);
v.append(i.ss-1);
u.append(r-1);
if(!c[{p-1,q-1}]){
a.append(p-1);
b.append(q-1);
c[{p-1,q-1}]=1;
}
else if(!c[{p-1,q+1}]){
a.append(p-1);
b.append(q+1);
c[{p-1,q+1}]=1;
}
else return 0;
}
}
r=z[{p,q-2}];
if(r){
if(!same(i.ss,r)){
merge(i.ss,r);
v.append(i.ss-1);
u.append(r-1);
if(!c[{p-1,q-1}]){
a.append(p-1);
b.append(q-1);
c[{p-1,q-1}]=1;
}
else if(!c[{p+1,q-1}]){
a.append(p+1);
b.append(q-1);
c[{p+1,q-1}]=1;
}
else return 0;
}
}
}
if(siz[root(1)]!=n) return 0;
build(u,v,a,b);
return 1;
}