oj.uz

Submission #712744

# Submission time Handle Problem Language Result Execution time Memory
712744 2023-03-19T16:45:45 Z fuad27 KOVANICE (COI15_kovanice) C++17
100 / 100
 329 ms 37044 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
struct DSU {
	vector<int> e;
	DSU(int N) { e = vector<int>(N, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool same_set(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) {
		x = get(x), y = get(y);
		if (x == y) return false;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y]; e[y] = x; return true;
	}
};
vector<int> g[N][2];
int res[N][2];
void dfs(int at, int b) {
	for(int to:g[at][b]) {
		if(!res[to][b])dfs(to,b);
		res[at][b]=max(res[to][b]+1,res[at][b]);
	}
}
int main () {
	cin.tie(0)->sync_with_stdio(0);
	int n, m, v;
	cin >> n >> m >> v;
	DSU d(m+1);
	int a[v], b[v];
	for(int i = 0;i<v;i++) {
		char c;
		cin >> a[i] >> c >> b[i];
		if(c=='=') {
			d.unite(a[i],b[i]);
			a[i]=-1,b[i]=-1;
		}
		else {
			if(c=='>')swap(a[i],b[i]);
		}
	}
	for(int i = 0;i<v;i++) {
		if(a[i]==-1)continue;
		g[d.get(a[i])][1].push_back(d.get(b[i]));
		g[d.get(b[i])][0].push_back(d.get(a[i]));
	}
	for(int i = 1;i<=m;i++) {
		dfs(d.get(i),1);dfs(d.get(i),0);
		if(res[d.get(i)][1]+res[d.get(i)][0]==n-1) {
			cout << "K" << res[d.get(i)][0]+1 << "\n";
		}
		else cout << "?\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 10 ms 14376 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 21708 KB Output is correct
2 Correct 80 ms 21988 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17096 KB Output is correct
2 Correct 32 ms 17100 KB Output is correct
3 Correct 31 ms 17076 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 33164 KB Output is correct
2 Correct 285 ms 32216 KB Output is correct
3 Correct 263 ms 32232 KB Output is correct
4 Correct 329 ms 36144 KB Output is correct
5 Correct 316 ms 37044 KB Output is correct