oj.uz

Submission #846394

# Submission time Handle Problem Language Result Execution time Memory
846394 2023-09-07T14:20:22 Z vjudge1 KOVANICE (COI15_kovanice) C++17
50 / 100
 242 ms 31540 KB 
#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 N = 1e5;
const int M = 3e5;

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] : nadj[u]) {
		dfs0(v);
	}

	topo.push_back(u);
}

int GLn;

bool vis1[M] = {};
int res[M] = {};
int curp = 0;
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;
	for (auto [_,v] : nadj[u]) {
		int re = dfs1(v, k+1);
		if (re != -1) {
			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].begin(), nadj[u].end());
	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 (!vis2[p]) dfs2(p);

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


	for (int p : topo) if (!vis1[p]) {
		curp = 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16732 KB Output is correct
2 Correct 5 ms 16732 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 23244 KB Output is correct
2 Correct 96 ms 23848 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 18888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 242 ms 31540 KB Output isn't correct
2 Halted 0 ms 0 KB -