oj.uz

Submission #58696

# Submission time Handle Problem Language Result Execution time Memory
58696 2018-07-18T22:23:42 Z reality Simurgh (IOI17_simurgh) C++17
13 / 100
 3000 ms 1049600 KB 
#include "simurgh.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 512;
int was[N * N];
int w[N][N];
int f[N];
vi g[N];
pii dfs(int node) {
	for (auto it : g[node])
		if (f[it] == -1 && !was[w[node][it]]) {
			f[it] = node;
			auto cnt = dfs(it);
			if (cnt != mp(-1,-1))
				return cnt;
		}
		else
		if (f[node] != it && f[it] != -1 && !was[w[node][it]])
			return mp(node,it);
	return mp(-1,-1);
}
int p[N];
int W[N];
int get(int k) {
	return k == p[k] ? k : p[k] = get(p[k]);
} 
vi find_roads(int n,vi u,vi v) {
	int m = u.size();
	for (int i = 0;i < m;++i)
		w[u[i]][v[i]] = w[v[i]][u[i]] = i,g[u[i]].pb(v[i]),g[v[i]].pb(u[i]);
	vi answer;
	for (int i = 0;i < n;++i)
		p[i] = i;
	vi ee;
	for (int i = 0;i < m;++i)
		if (get(u[i]) != get(v[i])) {
			ee.pb(i);
			p[get(u[i])] = get(v[i]);
		}
	do {
		vi cycle;
		for (int i = 0;i < n;++i) {
			for (int j = 0;j < n;++j)
				f[j] = -1;
			f[i] = i;
			auto cnt = dfs(i);
			if (cnt != mp(-1,-1)) {
				cycle.pb(w[cnt.fi][cnt.se]);
				for (int i = cnt.fi;i != cnt.se;i = f[i])
					cycle.pb(w[i][f[i]]);
				break;
			}
		}
		if (cycle.empty()) {
			break;
		} else {
			for (auto it : cycle)
				was[it] = 1;
			vi rs;
			for (int i = 0;i < cycle.size();++i) {
				for (int j = 0;j < n;++j)
					p[j] = j;
				vi e;
				for (int j = 0;j < cycle.size();++j)
					if (i != j) {
						p[get(u[cycle[j]])] = get(v[cycle[j]]);
						e.pb(cycle[j]);
					}
				for (auto it : ee)
					if (get(u[it]) != get(v[it])) {
						e.pb(it);
						p[get(u[it])] = get(v[it]);
					}
				rs.pb(count_common_roads(e));
			}
			int mn = *min_element(all(rs));
			int mx = *max_element(all(rs));
			if (mn != mx) {
				for (int i = 0;i < cycle.size();++i)
					if (rs[i] == mn)
						W[cycle[i]] = 1,was[cycle[i]] = 0;
			}
		}
	} while (1);
	for (int i = 0;i < m;++i)
		if (W[i] || (!W[i] && !was[i]))
			answer.pb(i);
	return answer;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:73:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0;i < cycle.size();++i) {
                   ~~^~~~~~~~~~~~~~
simurgh.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0;j < cycle.size();++j)
                    ~~^~~~~~~~~~~~~~
simurgh.cpp:92:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0;i < cycle.size();++i)
                    ~~^~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 3 ms 488 KB correct
3 Correct 3 ms 488 KB correct
4 Correct 3 ms 592 KB correct
5 Correct 2 ms 592 KB correct
6 Correct 3 ms 592 KB correct
7 Correct 3 ms 592 KB correct
8 Correct 2 ms 708 KB correct
9 Correct 2 ms 708 KB correct
10 Correct 2 ms 708 KB correct
11 Correct 3 ms 708 KB correct
12 Correct 3 ms 708 KB correct
13 Correct 3 ms 708 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 3 ms 488 KB correct
3 Correct 3 ms 488 KB correct
4 Correct 3 ms 592 KB correct
5 Correct 2 ms 592 KB correct
6 Correct 3 ms 592 KB correct
7 Correct 3 ms 592 KB correct
8 Correct 2 ms 708 KB correct
9 Correct 2 ms 708 KB correct
10 Correct 2 ms 708 KB correct
11 Correct 3 ms 708 KB correct
12 Correct 3 ms 708 KB correct
13 Correct 3 ms 708 KB correct
14 Execution timed out 3095 ms 1049600 KB Time limit exceeded
15 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 3 ms 488 KB correct
3 Correct 3 ms 488 KB correct
4 Correct 3 ms 592 KB correct
5 Correct 2 ms 592 KB correct
6 Correct 3 ms 592 KB correct
7 Correct 3 ms 592 KB correct
8 Correct 2 ms 708 KB correct
9 Correct 2 ms 708 KB correct
10 Correct 2 ms 708 KB correct
11 Correct 3 ms 708 KB correct
12 Correct 3 ms 708 KB correct
13 Correct 3 ms 708 KB correct
14 Execution timed out 3095 ms 1049600 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1049600 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 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 3 ms 488 KB correct
3 Correct 3 ms 488 KB correct
4 Correct 3 ms 592 KB correct
5 Correct 2 ms 592 KB correct
6 Correct 3 ms 592 KB correct
7 Correct 3 ms 592 KB correct
8 Correct 2 ms 708 KB correct
9 Correct 2 ms 708 KB correct
10 Correct 2 ms 708 KB correct
11 Correct 3 ms 708 KB correct
12 Correct 3 ms 708 KB correct
13 Correct 3 ms 708 KB correct
14 Execution timed out 3095 ms 1049600 KB Time limit exceeded
15 Halted 0 ms 0 KB -