Submission #105049

#	Time	Username	Problem	Language	Result	Execution time	Memory
105049		Shtef	KOVANICE (COI15_kovanice)	C++14	100 / 100	999 ms	39844 KiB

kovanice

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

typedef pair <int, int> pii;
#define x first
#define y second
#define mp make_pair

int n, m, v, link[300005], sz[300005], komp[300005], idx = 1, val[2][300005], ans[300005];
vector <int> ms[2][300005];
vector <pii> qrys;
bool bio[2][300005];

int find(int x){
	if(x == link[x])
		return x;
	return link[x] = find(link[x]);
}

bool same(int x, int y){
	return (find(x) == find(y));
}

void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(sz[x] < sz[y]){
		swap(x, y);
	}
	sz[x] += sz[y];
	link[y] = x;
}

void dfs(int x, bool di){
	if(bio[di][x])
		return;
	bio[di][x] = 1;
	val[di][x] = 1;
	for(vector <int>::iterator i = ms[di][x].begin() ; i != ms[di][x].end() ; ++i){
		int o = *i;
		dfs(o, di);
		val[di][x] = max(val[di][x], val[di][o] + 1);
	}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> v;
for(int i = 1 ; i <= m ; ++i){
	link[i] = i;
	sz[i] = 1;
}
for(int i = 0 ; i < v ; ++i){
	int x, y;
	char c;
	cin >> x >> c >> y;
	if(c == '<'){
		qrys.push_back(mp(x, y));
	}
	else{
		if(!same(x, y)){
			unite(x, y);
		}
	}
}
for(int i = 0 ; i < (int)qrys.size() ; ++i){
	int x = find(qrys[i].x), y = find(qrys[i].y);
	ms[0][y].push_back(x);
	ms[1][x].push_back(y);
}
for(int i = 1 ; i <= m ; ++i){
	int x = find(i);
	dfs(x, 0);
	dfs(x, 1);
}
for(int i = 1 ; i <= m ; ++i){
	int x = find(i);
	//cout << x << ' ' << val[0][x] << ' ' << val[1][x] << endl;
	ans[i] = (val[0][x] + val[1][x] != n + 1 ? -1 : val[0][x]);
}
for(int i = 1 ; i <= m ; ++i){
	if(ans[i] == -1){
		cout << "?" << endl;
	}
	else{
		cout << "K" << ans[i] << endl;
	}
}

return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40