oj.uz

Submission #902553

# Submission time Handle Problem Language Result Execution time Memory
902553 2024-01-10T17:07:18 Z LCJLY KOVANICE (COI15_kovanice) C++14
50 / 100
 2000 ms 30716 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<long long,long long>pii;

struct DSU{
	vector<int>e;
	void init(int n){
		e=vector<int>(n,-1);
	}
	
	int get(int x){return e[x]<0?x:e[x]=get(e[x]);}
	
	bool unite(int x, int y){
		x=get(x),y=get(y);
		if(x==y) return 0;
		if(e[x]>e[y]) swap(x,y);
		e[x]+=e[y];
		e[y]=x;
		return 1;
	}
};

int n,m,k;
vector<int>adj[300005];
int ans[300005];
vector<int>topo;
bool visited[300005];

void dfs(int index){
	visited[index]=true;
	for(auto it:adj[index]){
		if(visited[it]) continue;
		dfs(it);
	}
	topo.push_back(index);
}

int memo[300005];
int dp(int index){
	visited[index]=true;
	int ans=1;
	for(auto it:adj[index]){
		ans=max(ans,dp(it)+1);
	}
	
	return memo[index]=ans;
}

void color(int index, int d){
	ans[index]=n+1-d;
	for(auto it:adj[index]){
		if(memo[it]!=d-1) continue;
		color(it,d-1);
	}
}

void solve(){	
	cin >> n >> m >> k;
	
	DSU dsu;
	dsu.init(m+5);
	string s;
	vector<pii>edge;
	for(int x=0;x<k;x++){
		cin >> s;
		int a=0;
		int b=0;
		bool same=false;
		for(int y=0;y<(int)s.length();y++){
			if(s[y]=='='){
				same=true;
				b=a;
				a=0;
			}
			else if(s[y]=='<'){
				b=a;
				a=0;
			}
			else{
				int hold=s[y]-'0';
				a=a*10+hold;
			}			
		}
		
		if(same) dsu.unite(a,b);
		else{
			edge.push_back({b,a});
		}
	}
	
	for(auto it:edge){
		it.first=dsu.get(it.first);
		it.second=dsu.get(it.second);
		adj[it.first].push_back(it.second);
	}
	
	memset(ans,-1,sizeof(ans));
	memset(memo,-1,sizeof(memo));
	
	for(int x=1;x<=m;x++){
		//show2(x,x,dsu.get(x),dsu.get(x));
		if(dsu.get(x)==x&&!visited[x]){
			dfs(x);
		}
	}
	
	reverse(topo.begin(),topo.end());
	
	//show4(topo,topo);
	
	memset(visited,0,sizeof(visited));
	for(auto it:topo){
		if(visited[it]) continue;
		int hold=dp(it);
		if(hold==n) color(it,n);
	}
	
	for(int x=1;x<=m;x++){
		if(ans[dsu.get(x)]==-1){
			cout << "?\n";
		}
		else{
			cout << "K";
			cout << ans[dsu.get(x)] << "\n";
		}
	}
	
	
	
}	
 
int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12580 KB Output is correct
2 Correct 3 ms 12380 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 19804 KB Output is correct
2 Correct 40 ms 19916 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 15828 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2028 ms 30716 KB Time limit exceeded
2 Halted 0 ms 0 KB -