oj.uz

Submission #613963

# Submission time Handle Problem Language Result Execution time Memory
613963 2022-07-30T14:53:39 Z thezomb1e Simurgh (IOI17_simurgh) C++17
30 / 100
 3000 ms 4472 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define eb emplace_back
#define pb push_back
#define ft first
#define sd second
#define pi pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(...) dbg_out(__VA_ARGS__)

using ll = long long;
using ld = long double;
using namespace std;
using namespace __gnu_pbds;

//Constants
const ll INF = 5 * 1e18;
const int IINF = 2 * 1e9;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ld PI = 3.14159265359;

//Templates
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) {return os << '(' << p.first << ", " << p.second << ')';}
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) {os << '['; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << ']';}
void dbg_out() {cerr << endl;}
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << H << ' '; dbg_out(T...); }
template<typename T> void mins(T& x, T y) {x = min(x, y);}
template<typename T> void maxs(T& x, T y) {x = max(x, y);}
template<typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using omset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;


vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	int m = u.size();
	vector<vector<pi>> e(n);
	for (int i = 0; i < m; i++) {
		e[u[i]].pb({v[i], i});
		e[v[i]].pb({u[i], i});	
	}
	vector<bool> take(m + 5, false); vector<bool> vis(n, false);
	function<void(int, int)> dfs_build = [&](int f, int p) {
		vis[f] = true;
		for (const auto &[to, id] : e[f]) {
			if (!vis[to]) {
				take[id] = true;
				dfs_build(to, f);
			}
		}
	};
	dfs_build(0, -1);
	vector<int> cycle, col(n, 0), par(n, -1);
	function<bool(int, int)> dfs_cycle = [&](int f, int p) {
		col[f] = 1;
		for (const auto &[to, id] : e[f]) {
			if (!take[id] || to == p) continue;
			if (col[to] == 1) {
				int cur = f;
				cycle.pb(id);
				while (cur != to) {
					cycle.pb(par[cur]);
					if (u[par[cur]] == cur) {
						cur = v[par[cur]];
					} else {
						cur = u[par[cur]];
					}
				}
				return true;
			} else if (col[to] == 0) {
				par[to] = id;
				if (dfs_cycle(to, f)) return true;
			}
		}
		col[f] = 2;
		return false;
	};
	int init;
	{
		vector<int> ar;
		for (int i = 0; i < m; i++) {
			if (take[i]) ar.pb(i);
		}
		init = count_common_roads(ar);
	}
	vector<int> ans(m + 5, -1);
	for (int i = 0; i < m; i++) {
		if (take[i]) continue;
		cycle.clear();
		par.assign(n, -1);
		col.assign(n, 0);
		take[i] = true;
		dfs_cycle(0, -1);
		int found = -1;
		for (int edge : cycle) {
			if (ans[edge] != -1) {
				found = edge;
				break;
			}
		}
		if (found == -1) {
			for (int edge : cycle) {
				if (edge == i) continue;
				take[edge] = false;
				vector<int> ar;
				for (int j = 0; j < m; j++) {
					if (take[j]) ar.pb(j);
				}
				take[edge] = true;
				int val = count_common_roads(ar);
				if (val - init == 1) {
					ans[i] = 1; ans[edge] = 0;
					found = i;
					break;
				} else if (val - init == -1) {
					ans[i] = 0; ans[edge] = 1;
					found = i;
					break;
				}
			}
			if (ans[i] == -1) {
				ans[i] = 0;
				found = i;
			}
		}
		for (int edge : cycle) {
			if (ans[edge] != -1) continue;
			int bef, aft;
			{
				vector<int> ar;
				take[found] = false;
				for (int j = 0; j < m; j++) {
					if (take[j]) ar.pb(j);
				}
				take[found] = true;
				aft = count_common_roads(ar);
			}
			{
				vector<int> ar;
				take[edge] = false;
				for (int j = 0; j < m; j++) {
					if (take[j]) ar.pb(j);
				}
				take[edge] = true;
				bef = count_common_roads(ar);
			}
			if (ans[found] == 0) {
				if (aft - bef == 1) {
					ans[edge] = 1;
				} else {
					ans[edge] = 0;
				}
			} else {
				if (aft - bef == 0) {
					ans[edge] = 1;
				} else {
					ans[edge] = 0;
				}
			}
		}
		take[i] = false;
	}
	vector<int> ret;
	for (int i = 0; i < m; i++) {
		if ((take[i] && ans[i] == -1) || ans[i] == 1) {
			ret.pb(i);
		}
	}
	return ret;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 0 ms 296 KB correct
6 Correct 1 ms 296 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 17 ms 368 KB correct
15 Correct 16 ms 368 KB correct
16 Correct 17 ms 340 KB correct
17 Correct 11 ms 304 KB correct
18 Correct 2 ms 212 KB correct
19 Correct 11 ms 364 KB correct
20 Correct 10 ms 308 KB correct
21 Correct 8 ms 300 KB correct
22 Correct 6 ms 344 KB correct
23 Correct 5 ms 336 KB correct
24 Correct 5 ms 340 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 4 ms 212 KB correct
27 Correct 6 ms 212 KB correct
28 Correct 2 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 5 ms 340 KB correct
31 Correct 6 ms 296 KB correct
32 Correct 6 ms 296 KB correct
33 Correct 5 ms 340 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 0 ms 296 KB correct
6 Correct 1 ms 296 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 17 ms 368 KB correct
15 Correct 16 ms 368 KB correct
16 Correct 17 ms 340 KB correct
17 Correct 11 ms 304 KB correct
18 Correct 2 ms 212 KB correct
19 Correct 11 ms 364 KB correct
20 Correct 10 ms 308 KB correct
21 Correct 8 ms 300 KB correct
22 Correct 6 ms 344 KB correct
23 Correct 5 ms 336 KB correct
24 Correct 5 ms 340 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 4 ms 212 KB correct
27 Correct 6 ms 212 KB correct
28 Correct 2 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 5 ms 340 KB correct
31 Correct 6 ms 296 KB correct
32 Correct 6 ms 296 KB correct
33 Correct 5 ms 340 KB correct
34 Incorrect 2855 ms 1668 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 212 KB correct
2 Correct 1 ms 212 KB correct
3 Execution timed out 3047 ms 4472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 0 ms 296 KB correct
6 Correct 1 ms 296 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 17 ms 368 KB correct
15 Correct 16 ms 368 KB correct
16 Correct 17 ms 340 KB correct
17 Correct 11 ms 304 KB correct
18 Correct 2 ms 212 KB correct
19 Correct 11 ms 364 KB correct
20 Correct 10 ms 308 KB correct
21 Correct 8 ms 300 KB correct
22 Correct 6 ms 344 KB correct
23 Correct 5 ms 336 KB correct
24 Correct 5 ms 340 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 4 ms 212 KB correct
27 Correct 6 ms 212 KB correct
28 Correct 2 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 5 ms 340 KB correct
31 Correct 6 ms 296 KB correct
32 Correct 6 ms 296 KB correct
33 Correct 5 ms 340 KB correct
34 Incorrect 2855 ms 1668 KB WA in grader: NO
35 Halted 0 ms 0 KB -