Submission #104938

#	Time	Username	Problem	Language	Result	Execution time	Memory
104938		Shtef	KOVANICE (COI15_kovanice)	C++14	60 / 100	874 ms	42612 KiB

kovanice

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

using namespace std;

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

vector <int> ms[300005], fg[300005], topo[300005];
int n, m, v, link[300005], sz[300005], koja[300005], idx = 1, col[300005], val[300005];
vector <pii> a;
bool je[300005];

int tonumber(string s, int &x){
	int ret = 0;
	while(s[x] >= '0' && s[x] <= '9' && x < (int)s.size()){
		ret = ret * 10 + s[x] - '0';
		x++;
	}
	return ret;
}

int find(int x){
	while(x != link[x]){
		x = link[x];
	}
	return 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 dfs1(int x){
	koja[x] = idx;
	for(vector <int>::iterator i = fg[x].begin() ; i != fg[x].end() ; ++i){
		int o = *i;
		if(koja[o])
			continue;
		dfs1(o);
	}
}

void dfs2(int x){
	col[x] = 1;
	for(vector <int>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
		int o = *i;
		if(col[o] == 2)
			continue;
		if(col[o] == 1){
			je[koja[o]] = 1;
			continue;
		}
		dfs2(o);
	}
	col[x] = 2;
	topo[koja[x]].push_back(x);
}

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){
	string s;
	cin >> s;
	int sad = 0;
	int x = tonumber(s, sad);
	char c = s[sad];
	sad++;
	int y = tonumber(s, sad);
	if(c == '<'){
		a.push_back(mp(x, y));
	}
	else{
		if(!same(x, y)){
			unite(x, y);
		}
	}
}
for(int i = 0 ; i < (int)a.size() ; ++i){
	int x = a[i].x, y = a[i].y;
	x = find(x);
	y = find(y);
	ms[y].push_back(x);
	fg[x].push_back(y);
	fg[y].push_back(x);
}
for(int i = 1 ; i <= m ; ++i){
	sort(ms[i].begin(), ms[i].end());
	ms[i].resize(unique(ms[i].begin(), ms[i].end()) - ms[i].begin());
	sort(fg[i].begin(), fg[i].end());
	fg[i].resize(unique(fg[i].begin(), fg[i].end()) - fg[i].begin());
}
for(int i = 1 ; i <= m ; ++i){
	int x = find(i);
	if(koja[x])
		continue;
	dfs1(x);
	idx++;
}
for(int i = 1 ; i <= m ; ++i){
	int x = find(i);
	if(col[x])
		continue;
	dfs2(x);
}
for(int i = 1 ; i < idx ; ++i){
	reverse(topo[i].begin(), topo[i].end());
}
for(int i = 1 ; i <= m ; ++i){
	val[i] = 1;
}
for(int i = 1 ; i < idx ; ++i){
	int naj = 0;
	for(int j = (int)topo[i].size() - 1 ; j >= 0 ; --j){
		for(vector <int>::iterator v = ms[topo[i][j]].begin() ; v != ms[topo[i][j]].end() ; ++v){
			int o = *v;
			val[topo[i][j]] = max(val[topo[i][j]], val[o] + 1);
			naj = max(naj, val[topo[i][j]]);
		}
	}
	if(naj != n || je[i]){
		for(int j = 0 ; j < (int)topo[i].size() ; ++j){
			val[topo[i][j]] = -1;
		}
	}
}
for(int i = 1 ; i <= m ; ++i){
	int x = find(i);
	val[i] = val[x];
}
for(int i = 1 ; i <= m ; ++i){
	if(val[i] == -1){
		cout << "?" << endl;
	}
	else{
		cout << "K" << val[i] << endl;
	}
}

return 0;
}

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