Submission #712744

#	Time	Username	Problem	Language	Result	Execution time	Memory
712744		fuad27	KOVANICE (COI15_kovanice)	C++17	100 / 100	329 ms	37044 KiB

kovanice

#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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40