oj.uz

Submission #335191

# Submission time Handle Problem Language Result Execution time Memory
335191 2020-12-11T12:01:26 Z guka415 KOVANICE (COI15_kovanice) C++14
100 / 100
 415 ms 56512 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 21612 KB Output is correct
2 Correct 16 ms 21612 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 30444 KB Output is correct
2 Correct 128 ms 31980 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 23276 KB Output is correct
2 Correct 34 ms 24064 KB Output is correct
3 Correct 33 ms 24044 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 41708 KB Output is correct
2 Correct 328 ms 45036 KB Output is correct
3 Correct 321 ms 44652 KB Output is correct
4 Correct 363 ms 49772 KB Output is correct
5 Correct 415 ms 56512 KB Output is correct