oj.uz

Submission #105049

# Submission time Handle Problem Language Result Execution time Memory
105049 2019-04-10T10:06:52 Z Shtef KOVANICE (COI15_kovanice) C++14
100 / 100
 999 ms 39844 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14592 KB Output is correct
2 Correct 20 ms 14564 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 23672 KB Output is correct
2 Correct 431 ms 23892 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 17092 KB Output is correct
2 Correct 47 ms 17136 KB Output is correct
3 Correct 41 ms 17136 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 790 ms 32780 KB Output is correct
2 Correct 771 ms 34640 KB Output is correct
3 Correct 801 ms 34508 KB Output is correct
4 Correct 890 ms 39080 KB Output is correct
5 Correct 999 ms 39844 KB Output is correct