oj.uz

Submission #402478

# Submission time Handle Problem Language Result Execution time Memory
402478 2021-05-11T18:53:04 Z LucaDantas Simurgh (IOI17_simurgh) C++17
32 / 100
 142 ms 7828 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '['; string sep = ""; for (const auto &x : v) os << sep << x, sep = ", "; return os << ']'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename A> ostream& operator<<(ostream &os, const set<A> &s) { os << '{'; string sep = ""; for (const auto &x : s) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const map<A, B> &m) { os << '{'; string sep = ""; for (const auto &x : m) os << sep << x.first << " -> " << x.second, sep = ", "; return os << '}'; }

void debug() { cerr << endl; }
template<typename Ini, typename... Fim> void debug(Ini I, Fim... F) { cerr << I; if(sizeof...(F)) cerr << ", "; debug(F...);}
#define db(...) cerr << "DEBUG (" << #__VA_ARGS__ << ") == ", debug(__VA_ARGS__)

using pii = pair<int,int>;

#define pb push_back
#define ff first
#define ss second
#define sz(a) (int)(a.size())

constexpr int maxn = 510;

struct Edge
{
	int a, b, w, id; bool vis;
	friend ostream& operator<<(ostream& os, const Edge& e) {
		return os << e.a << ' ' << e.b << " == " << e.w;
		// return os << e.a << ' ' << e.b << ' ' << e.w << ' ' << e.id << ' ' << e.vis;
	}
};

vector<Edge> arvore;

int n, m, t;
int depth[maxn];
pii pai[maxn];

vector<pii> g[maxn], meus[maxn];

void dfs(int u) {
	// db(u, depth[u]);
	for(pii pp : g[u]) {
		auto [v, id] = pp;
		if(!depth[v]) {
			depth[v] = depth[u] + 1;

			arvore.pb({u, v, 0, id, 0});
			pai[v] = {u, t++};

			dfs(v);
		}
		else if(depth[v] > depth[u])
			meus[u].push_back(pp);
	}
}

void calc_tree() {
	vector<int> qry(n-1);
	for(int i = 0; i < t; i++)
		qry[i] = arvore[i].id;
	// db(t, qry);
	int base = count_common_roads(qry);
	// db(base);
	for(int u = 0; u < n; u++) {
		if(!meus[u].size()) continue;
		// db(u, meus[u]);

		int v = u, id = 0;
		for(pii aoba : meus[u])
			if(depth[aoba.ff] > depth[v]) v = aoba.ff, id = aoba.ss;

		// db(v, id);

		vector<int> ask, oto;

		for(int i = v; i != u; i = pai[i].ff) {
			int id_tree = pai[i].ss;
			if(!arvore[id_tree].vis) ask.push_back(id_tree), arvore[id_tree].vis = 1;
			else oto.push_back(id_tree);
		}

		if(!ask.size()) continue;

		if(oto.size()) {
			int e = oto.front();
			qry[e] = id;
			int eu = abs(count_common_roads(qry) - base) ^ arvore[e].w;
			qry[e] = arvore[e].id;

			for(const int& e : ask) {
				qry[e] = id;
				// db(qry, e, id);
				arvore[e].w = abs(count_common_roads(qry) - base) ^ eu;
				qry[e] = arvore[e].id;
			}
		} else {
			vector<int> ans;
			int mx = 0;
			for(int e : ask) {
				qry[e] = id;
				// db(qry, e, id);
				ans.pb(count_common_roads(qry) - base), mx = max(mx, ans.back());
				qry[e] = arvore[e].id;
			}

			int eu = mx;
			for(int i = 0; i < sz(ask); i++) {
				int e = ask[i];
				arvore[e].w = eu ^ abs(ans[i]);
			}
			// db(ask, ans);
		}
		// debug();
	}
}

struct DSU
{
	int pai[maxn], peso[maxn];
	void init() { for(int i = 0; i < n; i++) pai[i] = i, peso[i] = 1; }
	int find(int x) { return pai[x] == x ? x : pai[x] = find(pai[x]); }
	bool join(int a, int b) {
		a = find(a), b = find(b);
		if(a == b) return 0;
		if(peso[a] < peso[b]) swap(a, b);
		pai[b] = a;
		peso[a] += peso[b];
		return 1;
	}
} dsu;

pii edge[maxn*maxn];

int complete(vector<int>& base) {
	// db(base);
	dsu.init();
	for(int x : base)
		dsu.join(edge[x].ff, edge[x].ss);
	int custo = 0;
	for(Edge x : arvore)
		if(dsu.join(x.a, x.b))
			custo += x.w, base.pb(x.id);
	// db(base, custo);
	return custo;
}

vector<int> ans;
void solve(int u, int l, int r, int val) {
	if(!val) return;
	if(l == r) return (void)(ans.pb(meus[u][l].ss));
	int m = (l+r) >> 1;
	vector<int> gld;
	for(int i = l; i <= m; i++)
		gld.pb(meus[u][i].ss);
	int b = complete(gld);

	b = count_common_roads(gld) - b;
	solve(u, l, m, b);
	solve(u, m+1, r, val-b);
}

vector<int> find_roads(int N, vector<int> U, vector<int> V) {
	// db(U, V);
	n = N; m = (int)(U.size());
	for(int i = 0; i < m; i++) {
		g[U[i]].push_back({V[i], i});
		g[V[i]].push_back({U[i], i});
		edge[i] = {U[i], V[i]};
	}
	depth[0] = 1;

	dfs(0);

	calc_tree();

	for(auto& e : arvore) {
		e.w |= !e.vis;
		if(e.w) ans.pb(e.id);
	}

	// db(arvore);

	for(int u = 0; u < n; u++) {
		if(!meus[u].size()) continue;
		vector<int> gld;
		for(auto p : meus[u])
			gld.pb(p.ss);
		int b = complete(gld);
		b = count_common_roads(gld) - b;
		solve(u, 0, sz(meus[u])-1, b);
	}

	// db(ans);
	return ans;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 1 ms 332 KB correct
4 Correct 1 ms 332 KB correct
5 Correct 1 ms 332 KB correct
6 Correct 1 ms 332 KB correct
7 Correct 1 ms 332 KB correct
8 Correct 1 ms 332 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 332 KB correct
11 Correct 1 ms 332 KB correct
12 Correct 1 ms 332 KB correct
13 Correct 1 ms 332 KB correct
14 Correct 2 ms 332 KB correct
15 Correct 2 ms 332 KB correct
16 Correct 2 ms 332 KB correct
17 Correct 2 ms 332 KB correct
18 Correct 1 ms 332 KB correct
19 Correct 2 ms 332 KB correct
20 Correct 2 ms 332 KB correct
21 Correct 2 ms 332 KB correct
22 Correct 1 ms 332 KB correct
23 Correct 1 ms 332 KB correct
24 Correct 1 ms 332 KB correct
25 Correct 1 ms 332 KB correct
26 Correct 1 ms 336 KB correct
27 Incorrect 2 ms 332 KB WA in grader: NO
28 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 1 ms 332 KB correct
4 Correct 1 ms 332 KB correct
5 Correct 1 ms 332 KB correct
6 Correct 1 ms 332 KB correct
7 Correct 1 ms 332 KB correct
8 Correct 1 ms 332 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 332 KB correct
11 Correct 1 ms 332 KB correct
12 Correct 1 ms 332 KB correct
13 Correct 1 ms 332 KB correct
14 Correct 2 ms 332 KB correct
15 Correct 2 ms 332 KB correct
16 Correct 2 ms 332 KB correct
17 Correct 2 ms 332 KB correct
18 Correct 1 ms 332 KB correct
19 Correct 2 ms 332 KB correct
20 Correct 2 ms 332 KB correct
21 Correct 2 ms 332 KB correct
22 Correct 1 ms 332 KB correct
23 Correct 1 ms 332 KB correct
24 Correct 1 ms 332 KB correct
25 Correct 1 ms 332 KB correct
26 Correct 1 ms 336 KB correct
27 Incorrect 2 ms 332 KB WA in grader: NO
28 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 80 ms 4808 KB correct
4 Correct 125 ms 7696 KB correct
5 Correct 142 ms 7700 KB correct
6 Correct 73 ms 7620 KB correct
7 Correct 103 ms 7712 KB correct
8 Correct 109 ms 7696 KB correct
9 Correct 127 ms 7620 KB correct
10 Correct 139 ms 7712 KB correct
11 Correct 129 ms 7700 KB correct
12 Correct 128 ms 7700 KB correct
13 Correct 1 ms 332 KB correct
14 Correct 113 ms 7828 KB correct
15 Correct 127 ms 7632 KB correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 1 ms 332 KB correct
4 Correct 1 ms 332 KB correct
5 Correct 1 ms 332 KB correct
6 Correct 1 ms 332 KB correct
7 Correct 1 ms 332 KB correct
8 Correct 1 ms 332 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 332 KB correct
11 Correct 1 ms 332 KB correct
12 Correct 1 ms 332 KB correct
13 Correct 1 ms 332 KB correct
14 Correct 2 ms 332 KB correct
15 Correct 2 ms 332 KB correct
16 Correct 2 ms 332 KB correct
17 Correct 2 ms 332 KB correct
18 Correct 1 ms 332 KB correct
19 Correct 2 ms 332 KB correct
20 Correct 2 ms 332 KB correct
21 Correct 2 ms 332 KB correct
22 Correct 1 ms 332 KB correct
23 Correct 1 ms 332 KB correct
24 Correct 1 ms 332 KB correct
25 Correct 1 ms 332 KB correct
26 Correct 1 ms 336 KB correct
27 Incorrect 2 ms 332 KB WA in grader: NO
28 Halted 0 ms 0 KB -