Submission #1317332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317332		Ekber_Ekber	KOVANICE (COI15_kovanice)	C++20	50 / 100	157 ms	165192 KiB

kovanice

#include <bits/stdc++.h>
#define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;

constexpr int MAX = 2e+5 + 1, INF = 2e+16, MOD = 1e+9 + 7, K = 31;
int k;
deque <pair<int, int>> g[MAX+2];
vector <char> col(MAX+2, 0);
vector <int> is(MAX+2, 0);

bool dfs(int u, int d=1) {
	// cerr << "in " << u << endl;
	col[u]++;
	bool ok = 0;
	if (d == k) is[u] = k;
	for (auto &i : g[u]) {
		if (col[i.ff]) continue;
		if (dfs(i.ff, d+i.ss)) {
			is[u] = d;
		}
	}
	for (auto &i : g[u]) {
		if (is[i.ff]) is[u] = is[i.ff] - i.ss;
	}
	// cerr << "out " << u << ": " << is[u] << endl;
	return (is[u]);
}

struct DSU{
	int n;
	vector <int> par;
	void init(int n1) {
		n = n1;
		par.assign(n+1, -1);
	}
	int get(int u) {
		if (par[u] < 0) return u;
		return par[u] = get(par[u]);
	}
	bool un(int a, int b) {
		a = get(a);
		b = get(b);
		if(a == b) return 0;
		if (par[a] < par[b]) swap(a, b);
		par[b] += par[a];
		par[a] = b;
		return 1;
	}
};

void _() {
	int n, m;
	cin >> k >> n >> m;
	vector <pair<int, int>> v(n+1, {0, 0});
	DSU dsu;
	dsu.init(n);
	vector <pair<int, int>> e;
	while (m--) {
		int a, b;
		char c;
		cin >> a >> c >> b;
		if (c == '<') {
			e.pb({a, b});
		}
		else {
			dsu.un(a, b);
		}
	}
	for (auto &i : e) {
		int a = i.ff, b = i.ss;
		a = dsu.get(a);
		b = dsu.get(b);
		g[a].push_front({b, 1});
		g[b].pb({a, -1});
		v[a].ff--;
		v[b].ff++;
	}
	for (int i = 1; i <= n; i++) v[i].ss = i;
	sort(all(v));
	for (auto &i : v) {
		if (!col[dsu.get(i.ss)]) {
			dfs(dsu.get(i.ss));
		}
	}
	for (int i = 1; i <= n; i++) is[i] = is[dsu.get(i)];
	for (int i = 1; i <= n; i++) {
		if (is[i]) cout << "K" << is[i];
		else cout << "?";
		cout << endl;
	}
}

signed main() {

	GOOD_LUCK

	int tests=1;
	// cin >> tests;
	for (int i=1; i <= tests; i++) {
		_();
		cout << endl;
	}

	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40