Submission #137407

#	Time	Username	Problem	Language	Result	Execution time	Memory
137407		CaroLinda	Simurgh (IOI17_simurgh)	C++14	0 / 100	2 ms	632 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"

#define debug printf
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

const int MAXN = 510 ;
const int MAXM = 510*510 ;

using namespace std ;

struct Edge
{
	int j , id ;

	Edge(int j = 0 , int id = 0 )
		: j(j) , id(id) {}

} ;

int enterTime ;

int height[MAXN] , lowlink[MAXN] , ini[MAXN] , fim[MAXN] , pai[MAXN] ;

pii listEdges[MAXM] ;

vector<Edge> adj[MAXN] ;

bool isBridge[MAXM] , marc[MAXM] , royal[MAXN] ; 

vector<int> randomTree ;

// ----------------------------------

void dfs(int x, int depth )
{

	height[x] = lowlink[x] = depth ;

	for( Edge e : adj[x] )
	{

		if( marc[e.id] ) continue ;

		marc[e.id] = true ;

		if( height[e.j] != -1 )
		{ lowlink[x] = min( lowlink[x] , height[e.j] ) ; continue ; }

		dfs(e.j, depth+1 ) ;

		lowlink[x] = min( lowlink[e.j] , lowlink[x] ) ;

		if( lowlink[e.j] >= height[e.j] )
		{
			isBridge[e.id] = true ;
			royal[e.id] = true ;
		}

	}

}

void findRandomTree(int x)
{

	marc[x] = true ;
	ini[x] = ++ enterTime ;

	for( Edge e : adj[x] )
	{

		if( marc[e.j] ) continue ;

		randomTree.pb( e.id ) ;
		pai[e.j] = x ;

		findRandomTree(e.j) ;

	}

	fim[x] = enterTime ;


}
	

vector<int> find_roads(int n, vector<int> u, vector<int> v) 
{
	

	lp(i,0, u.size() )
	{

		int a = u[i] , b = v[i] ;

		adj[a].pb( Edge(b,i) ) ;
		adj[b].pb( Edge(a,i) ) ;

		listEdges[i] = mk(a,b) ;

	}

	memset( height, -1 , sizeof height ) ;

	dfs(0,1) ;
	pai[0] = -1 ;



	memset(marc, false, sizeof marc ) ;

	findRandomTree(0) ;

	lp(i,0,u.size())
	{

		int ini1 = listEdges[i].ff ;

		int ini2 = listEdges[i].ss ;

		if( ini1 < ini2 ) swap(listEdges[i].ff, listEdges[i].ss ) ;

	}

	int num = count_common_roads(randomTree) ;
	
	lp(g,0,randomTree.size() )
	{

		int i = randomTree[g] ;

		if( isBridge[i] ) continue ;



		bool imRoyal = true ;

		vector<int> equalToMe ; equalToMe.pb(i) ;

		pii p = listEdges[i] ;


		lp(j , 0, u.size())
		{

			if(isBridge[j]) continue ;

			if( !(ini[ listEdges[j].ff ] > ini[p.ff] && fim[listEdges[j].ss] <= fim[p.ff]) ) continue ;

			if( ini[listEdges[j].ss] > ini[p.ff] && fim[listEdges[j].ss] <= fim[p.ff] ) continue ;

			randomTree[g] = j ;

			int newNum = count_common_roads(randomTree) ;

			randomTree[g]  = i ;

			if(newNum == num) equalToMe.pb(j) ;

			else if(newNum > num)
			{
				royal[j] = true ;

				imRoyal = false ;
			}


		}

		if(imRoyal)
			for(int j : equalToMe)
				royal[j] = true ;

		
	}
	

	vector<int> ans ;

	lp(i,0, u.size() )
		if( royal[i] )
			ans.pb(i) ;

	return ans ;
	
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:5:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i=a;i<b;i++)
simurgh.cpp:98:5:
  lp(i,0, u.size() )
     ~~~~~~~~~~~~~               
simurgh.cpp:98:2: note: in expansion of macro 'lp'
  lp(i,0, u.size() )
  ^~
simurgh.cpp:5:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i=a;i<b;i++)
simurgh.cpp:121:5:
  lp(i,0,u.size())
     ~~~~~~~~~~~~                
simurgh.cpp:121:2: note: in expansion of macro 'lp'
  lp(i,0,u.size())
  ^~
simurgh.cpp:5:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i=a;i<b;i++)
simurgh.cpp:134:5:
  lp(g,0,randomTree.size() )
     ~~~~~~~~~~~~~~~~~~~~~       
simurgh.cpp:134:2: note: in expansion of macro 'lp'
  lp(g,0,randomTree.size() )
  ^~
simurgh.cpp:5:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i=a;i<b;i++)
simurgh.cpp:150:6:
   lp(j , 0, u.size())
      ~~~~~~~~~~~~~~~            
simurgh.cpp:150:3: note: in expansion of macro 'lp'
   lp(j , 0, u.size())
   ^~
simurgh.cpp:5:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i=a;i<b;i++)
simurgh.cpp:187:5:
  lp(i,0, u.size() )
     ~~~~~~~~~~~~~               
simurgh.cpp:187:2: note: in expansion of macro 'lp'
  lp(i,0, u.size() )
  ^~

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