Submission #496142

#	Time	Username	Problem	Language	Result	Execution time	Memory
496142		PedroBigMan	Simurgh (IOI17_simurgh)	C++14	0 / 100	1 ms	204 KiB

simurgh

/*
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 "simurgh.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 DSU //with range compression and union by subtree size
{
    public:
    ll N;
    vector<ll> p,siz;
    
    DSU(ll n)
    {
        N=n; REP(i,0,N) {p.pb(i); siz.pb(1);}
    }
    
    ll find(ll x)
    {
        if(p[x]==x) {return x;}
        ll ans=find(p[x]);
        p[x]=ans; 
        return ans;
    }
    
    void unionn(ll a, ll b)
    {
        a=find(a); b=find(b);
		if(a==b) {return;}
        if(siz[a]>siz[b]) {swap(a,b);}
        p[a]=b; siz[b]+=siz[a];
    }
	
	vector<vector<ll> > EquivalenceClasses() //O(N)
	{
		vector<vector<ll> > rep; REP(i,0,N) {rep.pb({});}
		REP(i,0,N) {rep[find(i)].pb(i);}
		vector<vector<ll> > CC; 
		REP(i,0,N) {if(rep[i].size()>0) {CC.pb(rep[i]);}}
		return CC;
	}
};

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

vector<int> find_roads(int n, vector<int> u, vector<int> v) 
{
	ll N=(ll) n; ll M = u.size();
	DSU D(N);
	vector<ll> in; VV(in,M,-1); ll ed=0;
	while(ed<N-1)
	{
		vector<vector<ll> > CC = D.EquivalenceClasses();
		vector<ll> rep; VV(rep,N,-1); REP(i,0,CC.size()) {REP(j,0,CC[i].size()) {rep[CC[i][j]]=i;}}
		vector<vector<ll> > adj; VV(adj,CC.size(),{});
		map<pl,vector<ll> > m; ll a,b;
		REP(i,0,M)
		{
			if(in[i]!=-1) {continue;}
			a=rep[u[i]]; b=rep[v[i]];
			if(m.find({a,b})==m.end()) {m[{a,b}]={}; m[{b,a}]={};}
			m[{a,b}].pb(i); m[{b,a}].pb(i);
		}
		map<pl,vector<ll> >::iterator it=m.begin();
		while(it!=m.end()) {adj[it->ff.ff].pb(it->ff.ss); it++;}
		Graph G(adj); G.Reset(); G.DFS_Tree(0); 
		ll leaf=0; REP(i,0,G.N) {if(G.dfs_tree[i].size()<=1) {leaf=i; break;}}
		vector<ll> c; REP(i,0,M) {if(in[i]==1) {c.pb(i);}}
		ll nei;
		REP(i,0,G.N) 
		{
			if(i==leaf) {continue;}
			REP(j,0,G.dfs_tree[i].size()) {nei=G.dfs_tree[i][j]; if(nei<i || nei==leaf) {continue;} c.pb(m[{i,nei}][0]);}
		}
		vector<pl> results; ll dummy;
		REP(i,0,adj[leaf].size())
		{
			nei=adj[leaf][i];
			REP(j,0,(m[{leaf,nei}].size()))
			{
				c.pb(m[{leaf,nei}][j]);
				//DEBUG(0); REP(z,0,c.size()) {cout<<"("<<u[c[z]]<<","<<v[c[z]]<<") ";}cout<<endl;
				dummy=count_common_roads(c); 
				results.pb({dummy,m[{leaf,nei}][j]});
				c.pop_back();
			}
		}
		sort(whole(results)); reverse(whole(results)); 
		ll edgeindex;
		REP(i,0,results.size())
		{
			edgeindex= results[i].ss;
			if(results[i].ff==results[0].ff) {D.unionn(u[edgeindex],v[edgeindex]); in[edgeindex]=1; ed++;}
			else {in[edgeindex]=0;}
		}
	}
	vector<ll> c; REP(i,0,M) {if(in[i]==1) {c.pb(i);}}
	return c;
}

Compilation message (stderr)

simurgh.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
simurgh.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      | 
simurgh.cpp: In constructor 'Graph::Graph()':
simurgh.cpp:94:17: warning: unused variable 'N' [-Wunused-variable]
   94 |     Graph() {ll N=0LL;}
      |                 ^

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30