Submission #846444

#	Time	Username	Problem	Language	Result	Execution time	Memory
846444		vjudge1	KOVANICE (COI15_kovanice)	C++17	60 / 100	225 ms	30448 KiB

kovanice

#include <bits/stdc++.h>
#define lint long long
#define endl '\n'
#define pii pair<int, int>
#define pll pair<lint, lint>
#define For(i,n) for (int i = 0; i < n; i++)
#define FOR For(i, n)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

const int M = 3e5+200;

int ds[M] = {};
int find(int x) {
	if (ds[x] < 0) return x;
	return ds[x] = find(ds[x]);
}
void merge(int a, int b) {
	int pa = find(a);
	int pb = find(b);
	if (ds[pb] < ds[pa]) swap(pa, pb);
	ds[pa] += ds[pb];
	ds[pb] = pa;
}

vector<int> adj[M];
vector<pii> nadj[M];

bool vis[M] = {};
vector<int> topo;
void dfs0(int u) {
	if (vis[u]) return;
	vis[u] = true;

	for (auto v : adj[u]) {
		dfs0(v);
	}

	topo.push_back(u);
}

int GLn;

bool vis1[M] = {};
int res[M] = {};
bool val[M] = {}; // valid?
int dfs1(int u, int k) {
	if (vis1[u]) return val[u] ? res[u]-1 : -1;
	vis1[u] = true;
	if (k == GLn) {
		res[u] = GLn;
		val[u] = 1;
		return k-1;
	}
	int toReturn = -1; int mx = nadj[u].size() ? nadj[u][0].first : 0;
	for (auto [_,v] : nadj[u]) {
		bool wasvis = vis1[v];
		int re = dfs1(v, k+1);
		if (re != -1 && (!wasvis || _ == mx)) {
			toReturn = re-1;
			res[u] = re;
			val[u] = true;
		}
	}

	return toReturn;
}

bool vis2[M] = {};
int mxs[M] = {};
int dfs2(int u) {
	if (vis2[u]) return mxs[u];
	vis2[u] = true;
	int mx = 0;
	for (int v : adj[u]) {
		int re = dfs2(v);
		mx = max(mx, 1 + re);
		nadj[u].push_back({re, v});
	}
	sort(nadj[u].rbegin(), nadj[u].rend());
	return mxs[u] = mx;
}

int main() {
	int n, m, v; cin >> n >> m >> v;

	GLn = n;

	For(i,M) ds[i] = -1;

	vector<pii> lesspairs;
	while (v--) {
		int a,b; char c; cin >> a >> c >> b;
		a--; b--;
		if (c != '=') {
			lesspairs.push_back({a,b});
			continue;
		}
		if (find(a) != find(b)) merge(a, b);
	}

	vector<int> parents;
	For(i,m) {
		if (ds[i] < 0) parents.push_back(i);
	}

	for (auto [a,b] : lesspairs) {
		adj[find(a)].push_back(find(b));
	}

	for (int p : parents) if (!vis[p]) dfs0(p);
	reverse(topo.begin(), topo.end());

	for (int p : topo) if (!vis2[p]) dfs2(p);

	for (int p : topo) if (!vis1[p]) {
		dfs1(p, 1);
	}

	For(i, m) {
		int parent = find(i);
		if (val[parent]) {
			cout << "K" << res[parent] << endl;
		} else cout << "?" << endl;
	}


}

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