Submission #495629

#	Time	Username	Problem	Language	Result	Execution time	Memory
495629		PedroBigMan	Fountain Parks (IOI21_parks)	C++17	0 / 100	0 ms	204 KiB

parks

/*
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 (stderr)

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;}
      |                 ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30