Submission #866508

#	Time	Username	Problem	Language	Result	Execution time	Memory
866508		abcdehello	KOVANICE (COI15_kovanice)	C++17	0 / 100	179 ms	29088 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;
int k,n,m,p[300050],vis[300050],d[300050],fix[300050];
vector<int> e[300050],topo;
int find(int u){
	if (p[u]!=u) p[u]=find(p[u]);
	return p[u];
}
void topoSort(int u){
	vis[u]=1;
	for (int v:e[u]) if (!vis[v]) topoSort(v);
	topo.push_back(u);
}
void dfs(int u){
	vis[u]=1;
	for (int v:e[u]){
		if (!vis[v]){
			fix[v]=fix[u]+1;
			dfs(v);
		}
	}
}
int main(){
	cin >> k >> n >> m;
	for (int i=1;i<=n;i++) p[i]=i;
	for (int i=0;i<m;i++){
		int u,v;
		char c;
		cin >> u >> c >> v;
		if (c=='<') e[u].push_back(v);
		else if (c=='>') e[v].push_back(u);
		else p[find(u)]=find(v);
	}
	for (int i=1;i<=n;i++){
		int par=find(i);
		for (int j:e[i]) e[par].push_back(find(j));
	}
	for (int i=1;i<=n;i++){
		if (find(i)!=i){
			e[i].clear();
			continue;
		}
		sort(e[i].begin(),e[i].end());
		e[i].erase(unique(e[i].begin(),e[i].end()),e[i].end());
	}
	for (int i=1;i<=n;i++){
		if (find(i)!=i) continue;
		if (vis[i]) continue;
		topoSort(i);
	}
	for (int i:topo){
		d[i]=k;
		for (int j:e[i]) d[i]=min(d[i],d[j]-1);
	}
	for (int i=1;i<=n;i++) vis[i]=0;
	for (int i=1;i<=n;i++){
		if (find(i)!=i) continue;
		if (d[i]==1) fix[i]=1,dfs(i);
	}
	for (int i=1;i<=n;i++){
		if (fix[find(i)]) cout << "K" << fix[find(i)] << "\n";
		else cout << "?\n";
	}
}

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