oj.uz

Submission #137405

# Submission time Handle Problem Language Result Execution time Memory
137405 2019-07-27T16:22:51 Z Lawliet Simurgh (IOI17_simurgh) C++14
0 / 100
 2 ms 632 KB 
#include <bits/stdc++.h>
#include "simurgh.h"

#define MAX 250

using namespace std;
typedef pair<int,int> pii;

int N, M;
int curTime;

int pai[MAX];
int low[MAX];
int prof[MAX];
int enterTime[MAX];
int paiEdge[MAX];
int isRoyal[MAX*MAX];//-1 => não fui calculado, 0 => não é real, 1 => é real

bool marc[MAX];
bool isBridge[MAX];
bool marcEdge[MAX*MAX];

pii edges[MAX*MAX];

vector<int> ans;

vector<int> grafo[MAX];
vector<int> indEdge[MAX];
vector<int> edgesWithout[MAX];

/*int count_common_roads(vector<int> r)
{
	for(int g = 0 ; g < N - 1 ; g++)
		printf("%d ",r[g]);

	printf("\n");
	int a;
	scanf("%d",&a);

	return a;
}*/

void DFS(int i, int p)
{
	marc[i] = true;
	low[i] = enterTime[i] = ++curTime;

	for(int g = 0 ; g < grafo[i].size() ; g++)
	{
		int prox = grafo[i][g];
		int ind = indEdge[i][g];

		if(marc[prox])
		{
			if(prox != p) low[i] = min(low[i] , enterTime[prox]);
			continue;
		}

		pai[prox] = i;
		paiEdge[prox] = ind;
		marcEdge[ind] = true;
		prof[prox] = prof[i] + 1;

		DFS(prox , i);

		if(low[prox] > enterTime[i])
		{
			isBridge[ind] = true;
			//printf("IISISS %d\n",ind);
		}

		low[i] = min(low[i] , low[prox]);
	}
}

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

	memset(isRoyal , -1 , sizeof(isRoyal));

	for(int g = 0 ; g < M ; g++)
	{
		int i = u[g];
		int j = v[g];

		grafo[ i ].push_back( j );
		grafo[ j ].push_back( i );

		indEdge[ i ].push_back( g );
		indEdge[ j ].push_back( g );

		edges[g] = {i , j};
	}	

	DFS( 0 , 0 );

	vector<int> test;

	for(int g = 1 ; g < n ; g++)
		test.push_back( paiEdge[g] );

	int qtdDFSTree = count_common_roads(test);

	if( qtdDFSTree == n - 1 ) return test;

	for(int g = 1 ; g < n ; g++)
		for(int h = 1 ; h < n ; h++)
			if(g != h) edgesWithout[ g ].push_back( paiEdge[h] );

	for(int g = 0 ; g < M ; g++)
	{
		if(marcEdge[ g ]) continue; //ESTA NA MINHA ARVORE DE DFS
		if(isBridge[g]) continue;
		if(isRoyal[g] != -1) continue;

		//printf("------------------------------------------ g = %d\n",g);

		int i = edges[g].first;
		int j = edges[g].second;

		if(prof[i] > prof[j]) swap(i , j);

		vector<pii> treeEdges;

		int cur = j;

		while(cur != i)
		{
			treeEdges.push_back( {paiEdge[cur] , cur} );
			//printf("COLOQUEI %d\n",cur);
			cur = pai[cur];
		}

		vector<int> qtd;

		int mx = -1;
		int monotone = -1;

		bool allEquals = true;

		for(int t = 0 ; t < treeEdges.size() ; t++)
		{
			int curBlocked = treeEdges[t].first;
			int nodeBlocked = treeEdges[t].second;

			//printf("BLOCKED    ------- %d\n",nodeBlocked);

			/*for(int k = 0 ; k < edgesWithout[nodeBlocked].size() ; k++)
				printf("ooo %d\n",edgesWithout[nodeBlocked][k]);*/

			edgesWithout[ nodeBlocked ].push_back( g );

			/*for(int k = 0 ; k < edgesWithout[nodeBlocked].size() ; k++)
				printf("oot %d\n",edgesWithout[nodeBlocked][k]);*/

			qtd.push_back( count_common_roads( edgesWithout[ nodeBlocked ] ) );

			if(g == 0) monotone = qtd.back();
			else if(monotone != qtd.back()) allEquals = false;

			if(qtd.back() == N - 1) return edgesWithout[nodeBlocked];

			mx = max(mx , qtd.back());

			edgesWithout[ nodeBlocked ].pop_back();

			//printf("passei\n");
		}

		if(allEquals)
		{
			//printf("djskdjlskdja\n");
			isRoyal[ g ] = 0;

			for(int h = 0 ; h < treeEdges.size() ; h++)
				isRoyal[ treeEdges[h].first ] = 0;
		}
		else
		{
			isRoyal[ g ] = 1;

			for(int h = 0 ; h < treeEdges.size() ; h++)
				if(qtd[h] != mx) isRoyal[ treeEdges[h].first ] = 1;
		}
	}

	for(int g = 0 ; g < M ; g++)
		if(isRoyal[g] == 1 || isBridge[g]) ans.push_back( g );

	return ans;
}

/*int main()
{
	int nn, mm;

	scanf("%d %d",&nn,&mm);

	vector<int> uu(mm), vv(mm);
	int n1, n2;

	for(int g = 0 ; g < mm ; g++)
		scanf("%d %d",&uu[g],&vv[g]);

	vector<int> aux = find_roads(nn , uu , vv);

	for(int g = 0 ; g < nn -1  ; g++)
		printf("%d\n",aux[g]);
}*/

Compilation message

simurgh.cpp: In function 'void DFS(int, int)':
simurgh.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < grafo[i].size() ; g++)
                  ~~^~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:142:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int t = 0 ; t < treeEdges.size() ; t++)
                   ~~^~~~~~~~~~~~~~~~~~
simurgh.cpp:144:8: warning: unused variable 'curBlocked' [-Wunused-variable]
    int curBlocked = treeEdges[t].first;
        ^~~~~~~~~~
simurgh.cpp:176:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int h = 0 ; h < treeEdges.size() ; h++)
                    ~~^~~~~~~~~~~~~~~~~~
simurgh.cpp:183:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int h = 0 ; h < treeEdges.size() ; h++)
                    ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 632 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 632 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 632 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB correct
2 Incorrect 2 ms 632 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 632 KB WA in grader: NO
2 Halted 0 ms 0 KB -