oj.uz

Submission #866506

# Submission time Handle Problem Language Result Execution time Memory
866506 2023-10-26T09:24:31 Z abcdehello KOVANICE (COI15_kovanice) C++17
0 / 100
 180 ms 33172 KB 
#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();
		sort(e[i].begin(),e[i].end());
		e[i].erase(unique(e[i].begin(),e[i].end()),e[i].end());
		//cerr << i << ": ";
		//for (int j:e[i]) cerr << j << " ";
		//cerr << endl;
	}
	for (int i=1;i<=n;i++){
		if (find(i)!=i) continue;
		if (vis[i]) continue;
		topoSort(i);
	}
	for (int i:topo){
		//cerr << i << " ";
		d[i]=k;
		for (int j:e[i]) d[i]=min(d[i],d[j]-1);
	}
	//cerr << endl;
	for (int i=1;i<=n;i++) vis[i]=0;
	for (int i=1;i<=n;i++){
		if (d[i]==1) fix[i]=1,dfs(i);
	}
	//for (int i=1;i<=n;i++) cerr << find(i) << " ";
	//cerr << endl;
	//for (int i=1;i<=n;i++) cerr << fix[i] << " ";
	//cerr << endl;
	for (int i=1;i<=n;i++){
		if (fix[find(i)]) cout << "K" << fix[find(i)] << "\n";
		else cout << "?\n";
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 17500 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 57 ms 23148 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 180 ms 33172 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -