oj.uz

Submission #298730

# Submission time Handle Problem Language Result Execution time Memory
298730 2020-09-13T21:37:07 Z keko37 Simurgh (IOI17_simurgh) C++14
0 / 100
 118 ms 5504 KB 
#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;
	while (lo != hi) {
		if (sol[pe[lo]] == -1) {
			cyc.push_back(pe[lo]);
		}
		lo = par[lo];
	}
	if (cyc.size() == 0) {
		lo = ea[ind];
		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;
		}
	}
}

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

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

Subtask #1
0 / 13.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB correct
2 Correct 1 ms 1024 KB correct
3 Incorrect 118 ms 5504 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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