oj.uz

Submission #250223

# Submission time Handle Problem Language Result Execution time Memory
250223 2020-07-17T08:48:40 Z srvlt Simurgh (IOI17_simurgh) C++14
30 / 100
 136 ms 6904 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 243, m0 = 29000;
int N, M, used[n0], ch[m0], par[n0], sp[m0], same[m0];
int in[n0], out[n0], T, common;
vector <int> g[n0], V, U, query;

void dfs(int v) {
	used[v] = 1;
	in[v] = ++T;
	for (int i : g[v]) {
		int to = V[i] ^ U[i] ^ v;
		if (used[to]) continue;
		par[to] = i;
		query.pb(i);
		sp[i] =  1;
		dfs(to);
	}
	out[v] = T;
}

bool upper(int v, int u) {
	return in[v] <= in[u] && out[u] <= out[v];
}

void add(int x) {
	query.pb(x);
}

void del(int x) {
	for (int i = 0; i < SZ(query); i++) {
		if (query[i] == x) {
			query.erase(query.begin() + i);
			break;
		}
	}
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	memset(& ch, -1, sizeof(ch));
	N = n, M = u.size(), V = v, U = u;
	for (int i = 0; i < M; i++)
		g[v[i]].pb(i), g[u[i]].pb(i);
	dfs(0);
	vector <int> path;
	common = count_common_roads(query);
	for (int i = 0; i < M; i++) {
		if (sp[i]) continue;
		int a = v[i], b = u[i];
		if (upper(b, a)) swap(a, b);
		assert(upper(a, b));
		path.clear();
		while (b != a) {
			path.pb(par[b]);
			b = v[par[b]] ^ u[par[b]] ^ b;
		}
		add(i);
		for (int j : path) {
			del(j);
			int x = count_common_roads(query);
			if (x == common) {
				same[j] = 1;
			}	else {
				if (x == common - 1) {
					ch[i] = 0;
					ch[j] = 1;
				}
				if (x == common + 1) {
					ch[i] = 1;
					ch[j] = 0;
				}
			}
			add(j);
		}
		if (ch[i] == -1) ch[i] = 0;
		del(i);
		for (int j : path) {
			if (same[j]) ch[j] = ch[i];
			same[j] = 0;
		}
	}
	vector <int> res;
	for (int i = 0; i < M; i++) {
		if (ch[i] == -1) ch[i] = 1;
		if (ch[i] == 1) res.pb(i);
	}
	return res;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 512 KB correct
3 Correct 1 ms 512 KB correct
4 Correct 0 ms 512 KB correct
5 Correct 0 ms 512 KB correct
6 Correct 0 ms 512 KB correct
7 Correct 0 ms 512 KB correct
8 Correct 1 ms 512 KB correct
9 Correct 1 ms 512 KB correct
10 Correct 1 ms 512 KB correct
11 Correct 0 ms 512 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 0 ms 384 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 512 KB correct
3 Correct 1 ms 512 KB correct
4 Correct 0 ms 512 KB correct
5 Correct 0 ms 512 KB correct
6 Correct 0 ms 512 KB correct
7 Correct 0 ms 512 KB correct
8 Correct 1 ms 512 KB correct
9 Correct 1 ms 512 KB correct
10 Correct 1 ms 512 KB correct
11 Correct 0 ms 512 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 0 ms 384 KB correct
14 Correct 20 ms 512 KB correct
15 Correct 21 ms 512 KB correct
16 Correct 21 ms 512 KB correct
17 Correct 17 ms 512 KB correct
18 Correct 7 ms 512 KB correct
19 Correct 17 ms 512 KB correct
20 Correct 16 ms 512 KB correct
21 Correct 16 ms 488 KB correct
22 Correct 8 ms 512 KB correct
23 Correct 7 ms 512 KB correct
24 Correct 6 ms 512 KB correct
25 Correct 1 ms 512 KB correct
26 Correct 7 ms 512 KB correct
27 Correct 7 ms 512 KB correct
28 Correct 2 ms 512 KB correct
29 Correct 1 ms 512 KB correct
30 Correct 11 ms 540 KB correct
31 Correct 11 ms 532 KB correct
32 Correct 11 ms 512 KB correct
33 Correct 11 ms 448 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 512 KB correct
3 Correct 1 ms 512 KB correct
4 Correct 0 ms 512 KB correct
5 Correct 0 ms 512 KB correct
6 Correct 0 ms 512 KB correct
7 Correct 0 ms 512 KB correct
8 Correct 1 ms 512 KB correct
9 Correct 1 ms 512 KB correct
10 Correct 1 ms 512 KB correct
11 Correct 0 ms 512 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 0 ms 384 KB correct
14 Correct 20 ms 512 KB correct
15 Correct 21 ms 512 KB correct
16 Correct 21 ms 512 KB correct
17 Correct 17 ms 512 KB correct
18 Correct 7 ms 512 KB correct
19 Correct 17 ms 512 KB correct
20 Correct 16 ms 512 KB correct
21 Correct 16 ms 488 KB correct
22 Correct 8 ms 512 KB correct
23 Correct 7 ms 512 KB correct
24 Correct 6 ms 512 KB correct
25 Correct 1 ms 512 KB correct
26 Correct 7 ms 512 KB correct
27 Correct 7 ms 512 KB correct
28 Correct 2 ms 512 KB correct
29 Correct 1 ms 512 KB correct
30 Correct 11 ms 540 KB correct
31 Correct 11 ms 532 KB correct
32 Correct 11 ms 512 KB correct
33 Correct 11 ms 448 KB correct
34 Incorrect 136 ms 1708 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 512 KB correct
3 Correct 1 ms 512 KB correct
4 Correct 0 ms 512 KB correct
5 Correct 0 ms 512 KB correct
6 Correct 0 ms 512 KB correct
7 Correct 0 ms 512 KB correct
8 Correct 1 ms 512 KB correct
9 Correct 1 ms 512 KB correct
10 Correct 1 ms 512 KB correct
11 Correct 0 ms 512 KB correct
12 Correct 1 ms 384 KB correct
13 Correct 0 ms 384 KB correct
14 Correct 20 ms 512 KB correct
15 Correct 21 ms 512 KB correct
16 Correct 21 ms 512 KB correct
17 Correct 17 ms 512 KB correct
18 Correct 7 ms 512 KB correct
19 Correct 17 ms 512 KB correct
20 Correct 16 ms 512 KB correct
21 Correct 16 ms 488 KB correct
22 Correct 8 ms 512 KB correct
23 Correct 7 ms 512 KB correct
24 Correct 6 ms 512 KB correct
25 Correct 1 ms 512 KB correct
26 Correct 7 ms 512 KB correct
27 Correct 7 ms 512 KB correct
28 Correct 2 ms 512 KB correct
29 Correct 1 ms 512 KB correct
30 Correct 11 ms 540 KB correct
31 Correct 11 ms 532 KB correct
32 Correct 11 ms 512 KB correct
33 Correct 11 ms 448 KB correct
34 Incorrect 136 ms 1708 KB WA in grader: NO
35 Halted 0 ms 0 KB -