oj.uz

Submission #137741

# Submission time Handle Problem Language Result Execution time Memory
137741 2019-07-28T09:19:37 Z MAMBA Simurgh (IOI17_simurgh) C++17
0 / 100
 2 ms 504 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;

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) {
			adj[dd.getPar(u[i])].pb(dd.getPar(v[i]));
			adj[dd.getPar(v[i])].pb(dd.getPar(u[i]));
		}

		int me = dfs(1);

		dsu ds;
		vi ask = local;
		for (auto e : ask) ds.merge(u[e] , v[e]);
		rep(i , 0 , m) 
			if (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) {
				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();
				}
			}
		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]]);
			}
	}

	return local;
}

Compilation message

simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:50: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 Correct 2 ms 256 KB correct
3 Runtime error 2 ms 380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 256 KB correct
3 Runtime error 2 ms 380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 256 KB correct
3 Runtime error 2 ms 380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 Correct 2 ms 256 KB correct
3 Runtime error 2 ms 380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -