oj.uz

답안 #138020

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
138020 2019-07-28T23:42:05 Z CaroLinda Simurgh (IOI17_simurgh) C++14
0 / 100
 2 ms 376 KB 
#include <bits/stdc++.h>
#include "simurgh.h"

#define debug 
#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) {}

} ;

vector<Edge> adj[MAXN] ;

vector<int> tree ;

bool marc[MAXN] , royal[MAXM] ;

int ini[MAXN] , fim[MAXN] ;

int Time ;

pii edge[MAXM] ;

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

bool isInside(int x , int y)
{

	return ( ini[x] > ini[y] && fim[x] <= fim[y] ) ;

}

void findRandomTree(int x)
{


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

	for(Edge e : adj[x])
		if(!marc[e.j])
		{
			tree.pb(e.id) ;
			findRandomTree(e.j) ;
		}

	fim[x] = Time ;

}

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

	int m = u.size() ;
	vector<int> ans ;

	lp(i,0,m)
	{

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

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

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

	}


	//Generating a random tree
	findRandomTree(0) ;
	for(int i : tree) debug("%d " , i ) ;
	debug("\n") ;
	lp(i,0,n) debug("%d %d\n" , ini[i] , fim[i]) ;

	//Sort the edges by child and parent
	//The first is the 'child' or candidate to it
	lp(i,0,m)
		if( ini[ edge[i].ff ] < ini[ edge[i].ss ] )
			swap( edge[i].ff , edge[i].ss ) ;


	int num  = count_common_roads(tree);

	//Trying to replace each edge
	for(int i = 0 ; i < n-1 ; i++ )
	{

		bool imRoyal = true ;

		int cur =  tree[i] ;
		int bigChild = edge[cur].ff ;

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

		

		lp(j,0,m)
		{

			//The 'child' must be inside bigChild subtree
			//The parent mustn't
			if( !isInside( edge[j].ff , bigChild ) || isInside( edge[j].ss , bigChild ) )
				continue ;

			tree[i] = j ;

			int newNum = count_common_roads(tree) ;

			tree[i] = cur ;

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

				imRoyal = false ;
			}


		}

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

	}


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

	return ans ;

}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:87:34: warning: left operand of comma operator has no effect [-Wunused-value]
  for(int i : tree) debug("%d " , i ) ;
                                  ^
simurgh.cpp:88:14: warning: statement has no effect [-Wunused-value]
  debug("\n") ;
              ^
simurgh.cpp:89:35: warning: left operand of comma operator has no effect [-Wunused-value]
  lp(i,0,n) debug("%d %d\n" , ini[i] , fim[i]) ;
                                   ^
simurgh.cpp:89:35: warning: right operand of comma operator has no effect [-Wunused-value]
  lp(i,0,n) debug("%d %d\n" , ini[i] , fim[i]) ;
                              ~~~~~^

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB correct
2 Incorrect 2 ms 376 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB WA in grader: NO
2 Halted 0 ms 0 KB -