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;
vector<vector<int>> adj;
vector<bool> vis;
const int MAX_X = 200000;
void dfs(int i)
{
if(vis[i])
return;
vis[i] = 1;
for(auto j : adj[i])
{
dfs(j);
}
}
int mn , mx , cur_x;
void dfs_comp(int i , vector<int> &y)
{
if(vis[i])
return ;
vis[i] = 1;
mn = min(mn , y[i]);
mx = max(mx , y[i]);
for(auto j : adj[i])
{
dfs_comp(j , y);
}
}
void add_edge(int u , int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n= (int)x.size();
adj.assign(n , {});
vis.assign(n , 0);
vector<int> u , v , a , b;
map<pair<int, int> , int> idx;
for(int i = 0 ; i <n ; i++)
{
idx[{x[i] , y[i]}] = i;
}
for(int i = 0 ; i < n ;i++)
{
if(idx.count({x[i] , y[i] + 2}))
{
u.push_back(i);
v.push_back(idx[{x[i] , y[i] + 2}]);
add_edge(u.back() , v.back());
b.push_back(y[i] + 1);
a.push_back(x[i] - 1);
}
}
vector<vector<int>> comp(MAX_X + 1);
for(int i = 0 ; i < n ;i++)
{
if(vis[i])
continue;
cur_x = x[i];
mn = 1e9;
mx = -1e9;
dfs_comp(i , y);
comp[cur_x].push_back(mn);
if(mx != mn)
comp[cur_x].push_back(mx);
}
for(int i = 2 ;i <= MAX_X ; i+=2)
{
sort(comp[i].begin() , comp[i].end());
}
for(int i = 4 ; i <= MAX_X ; i+=2)
{
for(int j = 0 ; j < (int)comp[i].size() ; j++)
{
int val = comp[i][j];
if(binary_search(comp[i - 2].begin() , comp[i - 2].end() , val))
{
u.push_back(idx[{i,val}]);
v.push_back(idx[{i - 2 , val}]);
add_edge(u.back() , v.back());
a.push_back(i - 1);
if(j % 2 == 0)
b.push_back(val - 1);
else
b.push_back(val + 1);
}
}
}
vis.assign(n , 0);
dfs(0);
for(int i = 0 ; i < n ; i++)
{
if(!vis[i])
{
return 0;
}
}
build(u , v , a , b);
return 1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |