oj.uz

Submission #137761

# Submission time Handle Problem Language Result Execution time Memory
137761 2019-07-28T09:27:57 Z MAMBA Simurgh (IOI17_simurgh) C++17
0 / 100
 2 ms 376 KB 
#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define pb push_back

typedef vector<int> vi;

const int N = 510;

struct dsu {
	int par[N];
	dsu() {
		iota(par , par + N, 0);
	}
	int getPar(int v) {
		return v == par[v] ? v : par[v] = getPar(par[v]);
	}
	inline bool merge(int a, int b) {
		if ((a = getPar(a)) == (b = getPar(b))) return false;
		par[a] = b;
		return true;
	}
};

dsu dd;
bitset<N> mark;
bitset<N * N> junk;

vi adj[N];

int dfs(int v) {
	mark[v] =true;
	int res = -1;
	for (auto e : adj[v])
		if (!mark[e]) {
			res = dfs(e);
			break;
		}
	if (res == -1) return v;
	return res;
}

vi find_roads(int n, vi u, vi v) {
	int m = u.size();

	vi local;

	while (local.size() < n - 1) {

		mark.reset();
		rep(i , 0 , n) adj[i].clear();
		rep(i , 0 , m) {
			if (junk[i]) continue;
			adj[dd.getPar(u[i])].pb(dd.getPar(v[i]));
			adj[dd.getPar(v[i])].pb(dd.getPar(u[i]));
		}

		int me = dfs(dd.getPar(0));

		dsu ds;
		vi ask = local;
		for (auto e : ask) ds.merge(u[e] , v[e]);
		rep(i , 0 , m) 
			if (!junk[i] && ds.getPar(u[i]) != me && ds.getPar(v[i]) != me && ds.merge(u[i] , v[i]))
				ask.pb(i);
		vi A, B;
		rep(i , 0 , m) {
			if (junk[i]) continue;
			int a = ds.getPar(u[i]);
			int b = ds.getPar(v[i]);
			if ((a == me && b != me) || (b == me && a != me)) {
				A.pb(i);
				ask.pb(i);
				B.pb(count_common_roads(ask));
				ask.pop_back();
			}
		}
		while (B.empty());
		int res = *max_element(B.begin(), B.end());
		rep(i , 0 , A.size()) {
			if (B[i] == res) {
				local.pb(A[i]);
				dd.merge(u[A[i]] , v[A[i]]);
			}
			else {
				junk[i] = true;
			}
		}
	}

	return local;
}

Compilation message

simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:51:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (local.size() < n - 1) {
         ~~~~~~~~~~~~~^~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory 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 #2
0 / 17.0

# Verdict Execution time Memory 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 #3
0 / 21.0

# Verdict Execution time Memory 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 #4
0 / 19.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -