Submission #298732

#	Time	Username	Problem	Language	Result	Execution time	Memory
298732		keko37	Simurgh (IOI17_simurgh)	C++14	51 / 100	153 ms	4984 KiB

simurgh

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

using namespace std;

typedef vector <int> vi;
typedef pair <int, int> pi;

const int MAXN = 505;
const int MAXM = 150005;

int n, m, uk;
int ea[MAXM], eb[MAXM], be[MAXM], pos[MAXM], sol[MAXM];
int bio[MAXN], par[MAXN], pe[MAXN], dub[MAXN];
int tmp[MAXN];
vector <pi> v[MAXN];
vi span;

void dfs (int x) {
	bio[x] = 1;
	for (auto pp : v[x]) {
		int sus = pp.first, ind = pp.second;
		if (sus == par[x]) continue;
		if (bio[sus]) {
			be[ind] = 1;
			continue;
		}
		par[sus] = x;
		dub[sus] = 1 + dub[x];
		pe[sus] = ind;
		pos[ind] = span.size();
		span.push_back(ind);
		dfs(sus);
	}
}

void obradi_back (int ind) {
	if (dub[ea[ind]] < dub[eb[ind]]) swap(ea[ind], eb[ind]);
	int lo = ea[ind], hi = eb[ind];
	vi cyc;
	bool naso = 0;
	while (lo != hi) {
		if (sol[pe[lo]] != -1) {
			naso = 1;
			break;
		}
		cyc.push_back(pe[lo]);
		lo = par[lo];
	}
	if (naso) {
		span[pos[pe[lo]]] = ind;
		if (count_common_roads(span) == uk) {
			sol[ind] = sol[pe[lo]];
		} else {
			sol[ind] = !sol[pe[lo]];
		}
		span[pos[pe[lo]]] = pe[lo];
	} else {
		int mn = uk, mx = uk;
		for (int i = 0; i < cyc.size(); i++) {
			span[pos[cyc[i]]] = ind;
			tmp[i] = count_common_roads(span);
			mx = max(mx, tmp[i]);
			mn = min(mn, tmp[i]);
			span[pos[cyc[i]]] = cyc[i];
		}
		if (mn == mx) {
			for (int i = 0; i < cyc.size(); i++) {
				sol[cyc[i]] = 0;
			}
			sol[ind] = 0;
		} else {
			for (int i = 0; i < cyc.size(); i++) {
				if (tmp[i] == mn) sol[cyc[i]] = 1; else sol[cyc[i]] = 0;
			}
			if (uk == mn) sol[ind] = 1; else sol[ind] = 0;
		}
	}
	lo = ea[ind];
	while (lo != hi) {
		if (sol[pe[lo]] == -1) {
			span[pos[pe[lo]]] = ind;
			if (count_common_roads(span) == uk) {
				sol[pe[lo]] = sol[ind];
			} else {
				sol[pe[lo]] = !sol[ind];
			}
			span[pos[pe[lo]]] = pe[lo];
		}
		lo = par[lo];
	}
}

vi find_roads (int N, vi U, vi V) {
	n = N; m = U.size();
	for (int i = 0; i < m; i++) {
		ea[i] = U[i], eb[i] = V[i];
		v[U[i]].push_back({V[i], i});
		v[V[i]].push_back({U[i], i});
	}
	dfs(0);
	par[0] = -1;
	uk = count_common_roads(span);
	memset(sol, -1, sizeof sol);
	for (int i = 0; i < m; i++) {
		if (be[i] == 1) {
			obradi_back(i);
		}
	}
	vi ans;
	for (int i = 0; i < m; i++) {
		if (sol[i] == 1 || sol[i] == -1) ans.push_back(i);
	}
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'void obradi_back(int)':
simurgh.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for (int i = 0; i < cyc.size(); i++) {
      |                   ~~^~~~~~~~~~~~
simurgh.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    for (int i = 0; i < cyc.size(); i++) {
      |                    ~~^~~~~~~~~~~~
simurgh.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |    for (int i = 0; i < cyc.size(); i++) {
      |                    ~~^~~~~~~~~~~~

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