oj.uz

Submission #846189

# Submission time Handle Problem Language Result Execution time Memory
846189 2023-09-07T12:16:01 Z vjudge1 KOVANICE (COI15_kovanice) C++17
0 / 100
 173 ms 21188 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)
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] = {};
void dfs1(int u, int k) {
	if (vis1[u]) return;
	vis1[u] = true;
	res[u] = k;
	mink[curp] = min(mink[curp], k);
	par[u] = curp;
	for (int v : adj[u]) {
		dfs1(v, k-1);
	}
}

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] = M+1;
		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;
	}


}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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