Submission #253151

#	Time	Username	Problem	Language	Result	Execution time	Memory
253151		Lawliet	Simurgh (IOI17_simurgh)	C++17	51 / 100	199 ms	3576 KiB

simurgh

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

using namespace std;

const int MAXN = 250;
const int MAXM = 30010;

int n, m;

int depth[MAXN];
int isRoyal[MAXM];
int ancNode[MAXN], ancEdge[MAXN];

bool mark[MAXN];
bool DFSTree[MAXM];

vector<int> tree;

vector<int> adj[MAXN];
vector<int> indEdge[MAXN];

void DFS(int cur)
{
	mark[cur] = true;

	for(int i = 0 ; i < (int)adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];
		int ind = indEdge[cur][i];

		if( mark[viz] ) continue;

		DFSTree[ind] = true;
		tree.push_back( ind );

		ancNode[viz] = cur;
		ancEdge[viz] = ind;
		depth[viz] = depth[cur] + 1;

		DFS( viz );
	}
}

int query(int newEdge = -1, int blockEdge = -1)
{
	vector<int> q;

	if( newEdge != -1 ) q.push_back( newEdge );

	for(int i = 0 ; i < (int)tree.size() ; i++)
		if( tree[i] != blockEdge ) q.push_back( tree[i] );

	return count_common_roads( q );
}

vector<int> find_roads(int N, vector<int> u, vector<int> v) 
{
	n = N; m = (int)u.size();

	for(int i = 0 ; i < m ; i++)
	{
		adj[ u[i] ].push_back( v[i] );
		adj[ v[i] ].push_back( u[i] );

		indEdge[ u[i] ].push_back( i );
		indEdge[ v[i] ].push_back( i );

		isRoyal[i] = -1;
	}

	DFS( 1 );

	int qtdRoyalTree = query();

	for(int i = 0 ; i < m ; i++)
	{
		if( DFSTree[i] ) continue;

		if( depth[ u[i] ] > depth[ v[i] ] )
			swap( u[i] , v[i] );

		int cur = v[i];
		int known = -1;

		vector<int> unknown;

		while( cur != u[i] )
		{
			if( isRoyal[ ancEdge[cur] ] != -1 ) known = ancEdge[cur];
			else unknown.push_back( ancEdge[cur] );

			cur = ancNode[cur];
		}

		if( known != -1 )
		{
			int newQtd = query( i , known );

			if( newQtd == qtdRoyalTree ) isRoyal[i] = isRoyal[known];
			else isRoyal[i] = 1 - isRoyal[known];

			for(int j = 0 ; j < (int)unknown.size() ; j++)
			{
				newQtd = query( i , unknown[j] );

				if( newQtd == qtdRoyalTree ) isRoyal[ unknown[j] ] = isRoyal[i];
				else isRoyal[ unknown[j] ] = 1 - isRoyal[i];
			}

			continue;
		}

		for(int j = 0 ; j < (int)unknown.size() ; j++)
		{
			int newQtd = query( i , unknown[j] );

			if( isRoyal[i] != -1 )
			{
				if( newQtd == qtdRoyalTree ) isRoyal[ unknown[j] ] = isRoyal[i];
				else isRoyal[ unknown[j] ] = 1 - isRoyal[i];

				continue;
			}

			if( newQtd != qtdRoyalTree )
			{
				if( newQtd > qtdRoyalTree ) isRoyal[i] = 1;
				else isRoyal[i] = 0;

				isRoyal[ unknown[j] ] = 1 - isRoyal[i];

				for(int k = 0 ; k < j ; k++)
					isRoyal[ unknown[k] ] = isRoyal[i];
			}
		}

		if( isRoyal[i] == -1 )
		{
			isRoyal[i] = 0;

			for(int j = 0 ; j < (int)unknown.size() ; j++)
				isRoyal[ unknown[j] ] = 0;
		}
	}

	for(int i = 0 ; i < m ; i++)
		if( isRoyal[i] == -1 ) isRoyal[i] = 1;

	vector<int> ans;

	for(int i = 0 ; i < m ; i++)
		if( isRoyal[i] == 1 ) ans.push_back( i );

	return ans;
}

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