oj.uz

Submission #846211

# Submission time Handle Problem Language Result Execution time Memory
846211 2023-09-07T12:30:56 Z vjudge1 KOVANICE (COI15_kovanice) C++17
50 / 100
 195 ms 21532 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];

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

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

	topo.push_back(u);
}

bool vis1[M] = {};
int mink[M] = {};
int res[M] = {};
int curp = 0;
int par[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 == 1) {
		res[u] = 1;
		val[u] = 1;
		return k+1;
	}
	res[u] = k;
	mink[curp] = min(mink[curp], k);
	par[u] = curp;
	int toReturn = -1;
	for (int v : adj[u]) {
		int re = dfs1(v, k-1);
		if (re != -1) {
			toReturn = re+1;
			res[u] = re;
			val[u] = true;
		}
	}

	return toReturn;
}

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

	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(b)].push_back(find(a));
	}

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

	for (int p : topo) if (!vis1[p]) {
		curp = p; mink[p] = n;
		dfs1(p, n);
	}

	For(i, m) {
		/*int w = find(i);
		int pi = par[w];
		if (mink[pi] != 1) {
			cout << "?\n";
			continue;
		}
		cout << "K" << res[w] << endl;*/
		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 3 ms 12632 KB Output is correct
2 Correct 3 ms 12632 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 16348 KB Output is correct
2 Correct 72 ms 16588 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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