/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
#include "parks.h"
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
#define VV(vvvv,NNNN,xxxx); REP(i,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
class Graph
{
public:
ll N;
vector<vector<ll> > adj;
vector<ll> visited; //for DFS/BFS
vector<vector<ll> > dfs_tree;
Graph() {ll N=0LL;}
Graph(vector<vector<ll> > ad)
{
adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false);}
VV(dfs_tree,N,{});
}
void Reset()
{
REP(i,0,N) {visited[i]=false;}
}
void DFS_Tree(ll s)
{
if(visited[s]) {return;}
visited[s]=true;
REP(i,0,adj[s].size())
{
if(!visited[adj[s][i]]) {dfs_tree[s].pb(adj[s][i]); dfs_tree[adj[s][i]].pb(s); DFS_Tree(adj[s][i]);}
}
return;
}
};
class DiGraph
{
public:
ll N;
vector<vector<ll> > adj;
vector<bool> visited;
vector<ll> current; //for CC
vector<ll> SCC; //Attributes a number to each node
vector<vector<ll> > adjK; //reverse graph, for Kosaraju
DiGraph(vector<vector<ll> > ad)
{
adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false); SCC.pb(-1LL);}
vector<ll> xx; REP(i,0,N) {adjK.pb(xx);}
REP(i,0,adj.size())
{
REP(j,0,adj[i].size()) {adjK[adj[i][j]].pb(i);}
}
}
void Reset()
{
REP(i,0,N) {visited[i]=false;}
current.clear();
}
void DFS(ll s)
{
if(visited[s]) {return;}
visited[s]=true;
REP(i,0,adj[s].size())
{
if(!visited[adj[s][i]]) {DFS(adj[s][i]);}
}
current.pb(s); //only needed for Kosaraju
return;
}
void DFSK(ll s)
{
if(visited[s]) {return;}
visited[s]=true;
REP(i,0,adjK[s].size())
{
if(!visited[adjK[s][i]]) {DFSK(adjK[s][i]);}
}
current.pb(s); //only needed for Kosaraju
return;
}
void Kosaraju()
{
if(SCC[0]!=-1) {return;}
Reset();
REP(i,0,N)
{
if(visited[i]) {continue;}
DFS(i);
}
vector<ll> List=current;
Reset();
ll c=0LL;
for(ll i=N-1LL;i>=0LL;i--)
{
ll node=List[i];
if(visited[node]) {continue;}
DFSK(node);
REP(j,0,current.size()) {SCC[current[j]]=c;}
c++;
current.clear();
}
}
DiGraph SCCGraph()
{
Kosaraju();
set<pl> ed;
REP(i,0,adj.size())
{
REP(j,0,adj[i].size())
{
ed.insert(mp(SCC[i],SCC[adj[i][j]]));
}
}
vector<vector<ll> > a; vector<ll> xx;
ll nscc=-INF; REP(i,0,N) {nscc=max(nscc,SCC[i]+1);}
REP(i,0,nscc) {a.pb(xx);}
set<pl>::iterator it=ed.begin();
pl cur;
while(it!=ed.end())
{
cur=*it;
if(cur.ff!=cur.ss) {a[cur.ff].pb(cur.ss);}
it++;
}
DiGraph ans(a);
return ans;
}
};
vector<bool> SAT2(ll N, vector<pl> a) //a[i] is j+1 if yes j, -j-1 if not j
{
ll M=a.size();
vector<vector<ll> > adj; vector<ll> xx; REP(i,0,2*N) {adj.pb(xx);}
pl c;
REP(i,0,M)
{
if(a[i].ff==-a[i].ss) {continue;}
c.ff = -a[i].ff; c.ss=a[i].ss;
if(c.ff<0) {c.ff=2*(-c.ff)-1;}
else {c.ff=2*c.ff-2;}
if(c.ss<0) {c.ss=2*(-c.ss)-1;}
else {c.ss=2*c.ss-2;}
adj[c.ff].pb(c.ss);
swap(a[i].ff,a[i].ss);
c.ff = -a[i].ff; c.ss=a[i].ss;
if(c.ff<0) {c.ff=2*(-c.ff)-1;}
else {c.ff=2*c.ff-2;}
if(c.ss<0) {c.ss=2*(-c.ss)-1;}
else {c.ss=2*c.ss-2;}
adj[c.ff].pb(c.ss);
}
DiGraph G(adj); G.Kosaraju();
vector<bool> ans; REP(i,0,N) {if(G.SCC[2*i]==G.SCC[2*i+1]) {return ans;}}
REP(i,0,N)
{
if(G.SCC[2*i]>G.SCC[2*i+1]) {ans.pb(true);}
else {ans.pb(false);}
}
return ans;
}
ll construct_roads(vector<ll> x, vector<ll> y)
{
ll N = x.size(); vector<vector<ll> > adj; VV(adj,N,{});
vector<pair<pl,ll> > p; REP(i,0,N) {p.pb({{x[i],y[i]},i});} sort(whole(p));
vector<pair<pl,ll> >::iterator it; ll nei;
REP(i,0,N)
{
it=lower_bound(whole(p),(pair<pl,ll>){{x[i]-2,y[i]},0});
if(it!=p.end())
{
nei=it->ss;
if(it->ff==(pl){x[i]-2,y[i]}) {adj[i].pb(nei); adj[nei].pb(i);}
}
it=lower_bound(whole(p),(pair<pl,ll>){{x[i]+2,y[i]},0});
if(it!=p.end())
{
nei=it->ss;
if(it->ff==(pl){x[i]+2,y[i]}) {adj[i].pb(nei); adj[nei].pb(i);}
}
it=lower_bound(whole(p),(pair<pl,ll>){{x[i],y[i]-2},0});
if(it!=p.end())
{
nei=it->ss;
if(it->ff==(pl){x[i],y[i]-2}) {adj[i].pb(nei); adj[nei].pb(i);}
}
it=lower_bound(whole(p),(pair<pl,ll>){{x[i],y[i]+2},0});
if(it!=p.end())
{
nei=it->ss;
if(it->ff==(pl){x[i],y[i]+2}) {adj[i].pb(nei); adj[nei].pb(i);}
}
}
Graph G(adj); G.Reset(); G.DFS_Tree(0);
vector<vector<ll> > tree = G.dfs_tree;
REP(i,0,N) {if(tree[i].size()==0) {return 0;}}
vector<ll> u,v;
REP(i,0,N)
{
REP(j,0,tree[i].size()) {if(i>tree[i][j]) {continue;} u.pb(i); v.pb(tree[i][j]);}
}
map<pair<pl,pl>,ll> m;
REP(i,0,N-1)
{
m[{{x[u[i]],y[u[i]]},{x[v[i]],y[v[i]]}}]=i;
m[{{x[v[i]],y[v[i]]},{x[u[i]],y[u[i]]}}]=i;
}
vector<pl> sat;
REP(i,0,N-1)
{
if(y[u[i]]!=y[v[i]]) {continue;}
if(m.find({{x[u[i]],y[u[i]]-2},{x[v[i]],y[v[i]]-2}})==m.end()) {continue;}
ll ind = m[{{x[u[i]],y[u[i]]-2},{x[v[i]],y[v[i]]-2}}];
//either i true or ind false
sat.pb({i+1,-ind-1});
}
REP(i,0,N-1)
{
if(x[u[i]]!=x[v[i]]) {continue;}
if(m.find({{x[u[i]]-2,y[u[i]]},{x[v[i]]-2,y[v[i]]}})==m.end()) {continue;}
ll ind = m[{{x[u[i]]-2,y[u[i]]},{x[v[i]]-2,y[v[i]]}}];
//either i true or ind false
sat.pb({i+1,-ind-1});
}
REP(i,0,N-1)
{
if(y[u[i]]!=y[v[i]]) {continue;}
if(m.find({{x[u[i]],y[u[i]]},{x[u[i]],y[u[i]]+2}})==m.end()) {continue;}
else {ll ind = m[{{x[u[i]],y[u[i]]},{x[u[i]],y[u[i]]+2}}]; sat.pb({-i-1,-ind-1});}
if(m.find({{x[u[i]],y[u[i]]},{x[u[i]],y[u[i]]-2}})==m.end()) {continue;}
else {ll ind = m[{{x[u[i]],y[u[i]]},{x[u[i]],y[u[i]]-2}}]; sat.pb({i+1,-ind-1});}
if(m.find({{x[v[i]],y[v[i]]},{x[v[i]],y[v[i]]+2}})==m.end()) {continue;}
else {ll ind = m[{{x[v[i]],y[v[i]]},{x[v[i]],y[v[i]]+2}}]; sat.pb({-i-1,ind+1});}
if(m.find({{x[v[i]],y[v[i]]},{x[v[i]],y[v[i]]-2}})==m.end()) {continue;}
else {ll ind = m[{{x[v[i]],y[v[i]]},{x[v[i]],y[v[i]]-2}}]; sat.pb({i+1,ind+1});}
}
vector<bool> ans = SAT2(N-1,sat);
if(ans.size()==0) {return 0;}
vector<ll> a,b;
REP(i,0,N-1)
{
if(x[u[i]]==x[v[i]]) //vertical
{
b.pb(min(y[u[i]],y[v[i]])+1);
if(ans[i])
{
a.pb(x[u[i]]+1);
}
else
{
a.pb(x[u[i]]-1);
}
}
else
{
a.pb(min(x[u[i]],x[v[i]])+1);
if(ans[i])
{
b.pb(y[u[i]]+1);
}
else
{
b.pb(y[u[i]]-1);
}
}
}
build(u,v,a,b);
return 1;
}
Compilation message
parks.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
5 | #pragma GCC optimization ("O3")
|
parks.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
6 | #pragma GCC optimization ("unroll-loops")
|
parks.cpp: In constructor 'Graph::Graph()':
parks.cpp:57:17: warning: unused variable 'N' [-Wunused-variable]
57 | Graph() {ll N=0LL;}
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
