Submission #1319861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319861		ElayV13	KOVANICE (COI15_kovanice)	C++20	100 / 100	422 ms	45840 KiB

kovanice

//g++ -o sol sol.cpp
//cd C:\Users\Asus-1\OneDrive\Desktop
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
const int INF = 1e18;
const int N = 300001;
#define S(a) a.begin(),a.end()
#define pb push_back
#define READ(l , r , a) for(int i = l;i <= r;i++) cin >> a[i]
#define printV(l , r , a) for(int i = l;i <= r;i++) cout << a[i] << ' ';
#define pii pair < int , int >
#define FOR(i , l , r) for(int i = l;i <= r;i++)
int n , m , e , head[N] , res[N];
vector < pii > edges;
vector < int > G[N] , F[N];
bool vis[N];
void dfs(int v , int h){
	head[v] = h;
	vis[v] = 1;
	for(int u : F[v]){
		if(!vis[u]) dfs(u , h);
	}
}
bool used[N];
vector < int > tp;
void tpsdfs(int v){
	used[v] = 1;
	for(int u : G[v]){
		if(!used[u]) tpsdfs(u);
	}
	tp.pb(v);
}
int ans[N];
bool vis2[N];
void DFS(int v , int cur){
	if(vis2[v]) return;
	vis2[v] = 1;
	ans[v] = cur;
	for(int u : G[v]){
		if(res[u] == cur - 1 && !vis2[u]) DFS(u , cur - 1);
	}
}
void solve(){
	cin >> n >> m >> e;
	for(int i = 1;i <= e;i++){
		int u; cin >> u;
		char c; cin >> c;
		int v; cin >> v;
		if(c != '='){
			if(c == '<') swap(u , v);
			edges.pb({u , v});
		}
		else{
			F[u].pb(v);
			F[v].pb(u);
		}
	}
	for(int i = 1;i <= m;i++){
		if(!vis[i]) dfs(i , i);
	}
	for(pair < int , int > edge : edges){
		int u = edge.first;
		int v = edge.second;
		u = head[u];
		v = head[v];
		G[u].pb(v);
	}
	for(int i = 1;i <= m;i++){
		if(!used[head[i]]){
			tpsdfs(head[i]);
		}
	}
	for(int v : tp){
		res[v] = 1;
		for(int u : G[v]){
			res[v] = max(res[v] , res[u] + 1);
		}
	}
	for(int i = 1;i <= m;i++){
		if(i != head[i]) continue;
		if(res[i] == n) DFS(i , n);
	}
	for(int i = 1;i <= m;i++){
		int node = head[i];
		if(!ans[node]){
			cout << "?" << endl;
			continue;
		}
		cout << "K" << ans[head[i]] << endl;
	}
}
signed main(){
        ios_base::sync_with_stdio();
        cin.tie(0);
	cout.tie(0);
	solve();	
}

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