| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 443486 | leinad2 | Fountain Parks (IOI21_parks) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#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;
}