Submission #846131

#	Time	Username	Problem	Language	Result	Execution time	Memory
846131		vjudge1	KOVANICE (COI15_kovanice)	C++17	0 / 100	348 ms	22212 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 7;
int n,m,v,depth[N],ans[N];
vector < int > graph[N];
struct DSU{
	vector < int > par;
	DSU(int x){
		par.resize(x+1);
		iota(par.begin() , par.end() , 0);
	}
	int find(int a){
		if(par[a] == a)return a;
		return par[a] = find(par[a]);
	}
	void merge(int a, int b){
		par[find(a)] = find(b);
	}
};
int find_depth(int node){
	if(depth[node] != -1)return depth[node];
	depth[node] = 1;
	for(auto itr : graph[node]){
		if(itr == node)continue;
		depth[node] = max(depth[node] , find_depth(itr) + 1);
	}
	return depth[node];
}
void investigate(int node , int dist){
	if(ans[node] != -1)return;
	ans[node] = dist;
	for(auto itr : graph[node]){
		if(itr == node)continue;
		if(depth[itr] == (dist-1)){
			investigate(itr,dist-1);
		}
	}
}
void solve(){
	memset(ans , -1 , sizeof(ans));
	memset(depth , -1 , sizeof(depth));
	cin >> n >> m >> v;
	DSU dsu(m);
	vector < string > query(v);
	for(auto &inp : query){
		cin >> inp;
		if(inp[1] == '='){
			int u = inp[0] - '0' , v = inp[2] - '0';
			dsu.merge(u,v);
		}
	}
	for(auto itr : query){
		int u = itr[0] - '0' , v = itr[2] - '0';
		if(itr[1] == '>'){
			graph[dsu.find(u)].push_back(dsu.find(v));
		}
		else{
			graph[dsu.find(v)].push_back(dsu.find(u));
		}
	}
	for(auto &itr : graph){
		sort(itr.begin() , itr.end());
		itr.resize(unique(itr.begin() , itr.end()) - itr.begin());
	}
	for(int i = 1;i<=m;i++){
		find_depth(dsu.find(i));
	}
	for(int i = 1;i<=m;i++){
		if(depth[dsu.find(i)] == n){
			investigate(dsu.find(i),n);
		}
	}
	for(int i = 1;i<=m;i++){
		if(ans[dsu.find(i)] == -1)cout << '?' << endl;
		else cout << 'K' << ans[dsu.find(i)] << endl;
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

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