Submission #335191

#	Time	Username	Problem	Language	Result	Execution time	Memory
335191		guka415	KOVANICE (COI15_kovanice)	C++14	100 / 100	415 ms	56512 KiB

kovanice

#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (long long i = k; i < n; i++)
#define ford(i, k, n) for (long long i = k; i >= n; i--)
#define pb push_back
#define mp make_pair

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <bitset>
#include <queue>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;

const int sz = 3e5 + 5;

pair<pii, char> parse(string s) {
	int cur = 0, ind = 0, len = s.length();
	pair<pii, char> ret;
	while (ind < len&&s[ind] >= '0'&&s[ind] <= '9') {
		cur *= 10;
		cur += (s[ind++] - '0');
	}
	ret.first.first = cur;
	ret.second = s[ind++];
	cur = 0;
	while (ind < len&&s[ind] >= '0'&&s[ind] <= '9') {
		cur *= 10;
		cur += (s[ind++] - '0');
	}
	ret.first.second = cur;
	return ret;
}

struct dsu {
	int f[sz], p[sz];
	int nn;
	dsu(int size) {
		nn = size;
		foru(i, 0, nn) {
			p[i] = 1;
			f[i] = i;
		}
	}
	int father(int src) {
		while (src != f[src])return f[src] = father(f[src]);
		return src;
	}
	bool unite(int a, int b) {
		int fa = father(a), fb = father(b);
		if (fa == fb)return false;
		if (p[fa] < p[fb])swap(fa, fb);
		f[fb] = fa;
		p[fa] = max(p[fb] + 1, p[fa]);
		return true;
	}
};

vector<int> unadj[sz], adj[sz], radj[sz];
int coins, mirk, v, ans[sz], indeg[sz], dp[sz];
dsu* d;
bitset<sz> isf, vis;

void input() {
	cin >> coins >> mirk >> v;
	d = new dsu(mirk);
	foru(i, 0, v) {
		string s;
		cin >> s;
		pair<pii, char> p = parse(s);
		p.first.first--; p.first.second--;
		switch (p.second) {
		case '=':
			d->unite(p.first.first, p.first.second);
			break;
		case '<':
			unadj[p.first.first].pb(p.first.second);
			break;
		}
	}
	foru(i, 0, mirk) {
		int myf = d->father(i);
		isf[myf] = 1;
		for (int x : unadj[i]) {
			int otherf = d->father(x);
			adj[myf].pb(otherf); radj[otherf].pb(myf);
			indeg[otherf]++;
		}
	}
}

void dfs(int src) {
	vis[src] = 1;
	ans[src] = dp[src];
	for (int x : radj[src]) {
		if (!vis[x] && dp[x] == dp[src] - 1)dfs(x);
	}
}

int main() {
	fast;
	input();
	queue<int> q;
	foru(i, 0, mirk) {
		if (isf[i] && indeg[i] == 0)q.push(i);
	}
	while (!q.empty()) {
		int x = q.front(); q.pop();
		dp[x] = 1;
		for (int y : radj[x])dp[x] = max(dp[x], dp[y] + 1);
		for (int y : adj[x]) {
			indeg[y]--;
			if (indeg[y] == 0)q.push(y);
		}
	}
	foru(i, 0, mirk) {
		if (dp[i] == coins)dfs(i);
	}
	foru(i, 0, mirk) {
		int myf = d->father(i);
		if (ans[myf] != 0)cout << 'K' << to_string(ans[myf]) << '\n';
		else cout << "?\n";
	}
	return 0;
}

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