#include<bits/stdc++.h>
#include "parks.h"
using namespace std;
struct Edge
{
int som,ind;
};
map<pair<int,int>,int>M,M2;
vector<Edge>Graf[200009];
vector<int>D[1000009];
pair<int,int>KimJest[1000009];
bool zaj[1000009];
vector<int>Sprz;
int g[1000009];
int match[1000009];
int n,m=0,k=0,N,IleVert=0;
int f[200009],ilosc[200009];
bool Zaj[1000009];
int F(int v)
{
if(f[v]==v){return v;}
return f[v]=F(f[v]);
}
void Polacz(int a, int b)
{
a=F(a);
b=F(b);
if(a==b){return;}
if(ilosc[a]<ilosc[b]){swap(a,b);}
ilosc[a]+=ilosc[b];
f[b]=a;
}
bool DFS(int v)
{
if(zaj[v]){return 0;}
zaj[v]=1;
Sprz.push_back(v);
for(int som : D[v])
{
if(match[som]==-1||DFS(match[som]))
{
match[v]=som;
match[som]=v;
return 1;
}
}
return 0;
}
void BFS()
{
int start=rand()%N;
Zaj[start]=1;
deque<int>Y;
Y.push_back(start);
while((int)Y.size()>0)
{
const int v=Y[0];
Y.pop_front();
for(int som : D[v])
{
if(Zaj[som]==0)
{
Zaj[som]=1;
Y.push_back(som);
if(match[v]==-1&&match[som]==-1)
{
match[v]=som;
match[som]=v;
}
}
}
}
}
void SKOJ()
{
random_shuffle(g,g+N);
for(int i=0;i<N;i++)
{
zaj[i]=0;
}
BFS();
random_shuffle(g,g+N);
return;
for(int i=0;i<N;i++)
{
int u=g[i];
if(match[u]==-1)
{
DFS(u);
}
for(int temp : Sprz)
{
zaj[temp]=0;
}
Sprz.clear();
}
}
void Upgrade(int v)
{
zaj[v]=1;
Sprz.push_back(v);
for(int som : D[v])
{
if(zaj[match[som]]==0)
{
Upgrade(match[som]);
match[v]=som;
match[som]=v;
return;
}
else if(match[som]!=v)
{
break;
}
}
for(int u : Sprz){zaj[u]=0;}
Sprz.clear();
match[v]=-1;
}
void CzySpojna(int v)
{
zaj[v]=1;
IleVert++;
for(auto[som,ind] : Graf[v])
{
if(zaj[som]){continue;}
CzySpojna(som);
}
}
int construct_roads(vector<int>X, vector<int>Y)
{
srand(2137);
n=(int)X.size();
for(int i=0;i<n;i++)
{
M[{X[i],Y[i]}]=i;
}
for(int i=0;i<n;i++)
{
if(M.find({X[i]-2,Y[i]})!=M.end())
{
Graf[i].push_back({M[{X[i]-2,Y[i]}],m});
Graf[M[{X[i]-2,Y[i]}]].push_back({i,m});
m++;
}
if(M.find({X[i],Y[i]-2})!=M.end())
{
Graf[i].push_back({M[{X[i],Y[i]-2}],m});
Graf[M[{X[i],Y[i]-2}]].push_back({i,m});
m++;
}
}
CzySpojna(0);
if(IleVert!=n){return 0;}
vector<pair<int,int>>E(m);
for(int i=0;i<n;i++)
{
for(auto[som,ind] : Graf[i])
{
int a=i,b=som;
if(pair<int,int>{X[a],Y[a]}>pair<int,int>{X[b],Y[b]}){continue;}
E[ind]={a,b};
}
}
for(int i=0;i<(int)E.size();i++)
{
const int a=E[i].first,b=E[i].second;
vector<pair<int,int>>Som;
if(Y[a]+2==Y[b])
{
Som.push_back({X[a]-1,Y[a]+1});
Som.push_back({X[a]+1,Y[a]+1});
}
else if(X[a]+2==X[b])
{
Som.push_back({X[a]+1,Y[a]+1});
Som.push_back({X[a]+1,Y[a]-1});
}
for(pair<int,int>som : Som)
{
if(M2.find(som)==M2.end())
{
KimJest[k]=som;
M2[som]=k++;
}
int u=m+M2[som];
D[i].push_back(u);
D[u].push_back(i);
}
}
N=m+k;
for(int i=0;i<N;i++){g[i]=i;}
for(int i=0;i<N;i++)
{
match[i]=-1;
}
SKOJ();
for(int I=1;true;I++)
{
for(int i=0;i<n;i++)
{
f[i]=i;
ilosc[i]=1;
}
for(int i=0;i<n;i++)
{
for(auto[som,ind] : Graf[i])
{
if(match[ind]==-1){continue;}
Polacz(i,som);
}
}
if(ilosc[F(0)]==n)
{
vector<int>O1,O2,O3,O4;
for(int j=0;j<m;j++)
{
const int a=E[j].first,b=E[j].second;
if(match[j]!=-1)
{
pair<int,int>xd=KimJest[match[j]-m];
O1.push_back(a);
O2.push_back(b);
O3.push_back(xd.first);
O4.push_back(xd.second);
}
}
build(O1,O2,O3,O4);
return 1;
}
vector<int>U;
for(int i=0;i<n;i++){g[i]=i;}
random_shuffle(g,g+n);
for(int i=0;i<n;i++)
{
const int u=g[i];
for(auto[som,ind] : Graf[u])
{
if(match[ind]==-1&&F(u)!=F(som))
{
U.push_back(ind);
Polacz(u,som);
}
}
}
if(I%5==0)
{
for(int i=0;i<N;i++)
{
match[i]=-1;
}
for(int u : U)
{
for(int som : D[u])
{
if(match[u]==-1&&match[som]==-1)
{
match[u]=som;
match[som]=u;
}
}
}
SKOJ();
continue;
}
for(int u : U)
{
if(match[u]!=-1){continue;}
Upgrade(u);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
57692 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
57692 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
57692 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
57692 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
57692 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
57692 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
