| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 443486 | leinad2 | 분수 공원 (IOI21_parks) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
int par[400010], chk[400010], chk2[400010], A[400010][2], vis[400010];
int Find(int v){return v==par[v]?v:par[v]=Find(par[v]);}
vector<pair<int, int> >v;
int cnt;
map<pair<int, int>, int>mp;
vector<pair<int, int> >adj[400010];
vector<int>_u, _v, _a, _b;
void dfs(int v)
{
for(int i=0;i<adj[v].size();i++)
{
int p=adj[v][i].first;
if(!vis[p])vis[p]=1,dfs(p),_a[adj[v][i].second]=p;
}
}
int construct_roads(vector<int>x, vector<int>y)
{
int n, i, j, k, a, b;
n=x.size();
vector<pair<pair<int, int>, int> >V;
for(i=0;i<n;i++)
{
V.push_back({{x[i], y[i]}, i});
}
sort(V.begin(), V.end());
for(i=1;i<V.size();i++)
{
if(V[i].first.first==V[i-1].first.first&&V[i].first.second==V[i-1].first.second+2)
{
v.push_back({V[i].second, V[i-1].second});
}
}
for(i=0;i<n;i++)
{
swap(V[i].first.first, V[i].first.second);
}
sort(V.begin(), V.end());
for(i=1;i<V.size();i++)
{
if(V[i].first.first==V[i-1].first.first&&V[i].first.second==V[i-1].first.second+2)
{
v.push_back({V[i].second, V[i-1].second});
}
}
for(int rng=0;rng<1;rng++)
{
for(i=0;i<n;i++)par[i]=i;
_u.clear();_v.clear();_a.clear();_b.clear();cnt=0;mp.clear();for(i=1;i<=2*n;i++)vis[i]=chk[i]=chk2[i]=0,adj[i].clear();
for(i=0;i<v.size();i++)
{
if(Find(v[i].first)!=Find(v[i].second))
{
_u.push_back(v[i].first);
_v.push_back(v[i].second);
par[Find(v[i].first)]=Find(v[i].second);
}
}
if(_u.size()!=n-1)return 0;
vector<pair<int, int> >edge;
_a.resize(n-1);_b.resize(n-1);
for(i=0;i<_u.size();i++)
{
int a=_u[i], b=_v[i], q, w, e, r;
if(x[a]==x[b])
{
q=x[a]-1;e=x[a]+1;
w=r=(y[a]+y[b])/2;
}
else
{
w=y[a]-1;r=y[a]+1;
q=e=(x[a]+x[b])/2;
}
if(mp.find({q, w})==mp.end())mp[{q, w}]=++cnt,A[cnt][0]=q,A[cnt][1]=w;
if(mp.find({e, r})==mp.end())mp[{e, r}]=++cnt,A[cnt][0]=e,A[cnt][1]=r;
int x=mp[{q, w}];int y=mp[{e, r}];
edge.push_back({x, y});
}
for(i=0;i++<cnt;)par[i]=i;
for(i=0;i<edge.size();i++)par[Find(edge[i].first)]=Find(edge[i].second);
for(i=0;i++<cnt;)chk[Find(i)]++;
for(i=0;i<edge.size();i++)chk2[Find(edge[i].first)]++;
for(i=0;i<edge.size();i++)
{
adj[edge[i].first].push_back({edge[i].second, i});
adj[edge[i].second].push_back({edge[i].first, i});
}
bool flag=true;
for(i=0;i++<cnt;)
{
if(chk[i])
{
if(chk[i]<chk2[i]){flag=false;break;}
else vis[i]=1,dfs(i);
}
}
if(!flag)continue;
for(i=0;i<_a.size();i++)
{
if(_a[i]==0)_a[i]=Find(edge[i].first);
int a=_a[i];
_a[i]=A[a][0];_b[i]=A[a][1];
}
build(_u, _v, _a, _b);
return 1;
}
return 0;
}