제출 #1319841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319841		ElayV13	KOVANICE (COI15_kovanice)	C++20	50 / 100	2096 ms	31512 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];
int par[N];
void DFS(int v , int p , int cd){
	par[v] = p;
	if(used[v] && res[v] + cd - 1 == n){
		if(!G[v].size()) res[v] = 1;
		int cur = v , cr = res[v];
		while(1){
			res[cur] = cr;
			cr++;
			cur = par[cur];
			if(cr > n or !used[cur]) break;
		}
		return;
	}
	used[v] = 1;
	if(cd == n){
		int cur = v , cr = 1;
		while(1){
			res[cur] = cr;
			cr++;
			cur = par[cur];
			if(cr > n) break;
		}
		return;
	}
	for(int u : G[v]){
		DFS(u , v , cd + 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]]) DFS(head[i] , -1 , 1);
	}
	for(int i = 1;i <= m;i++){
		int node = head[i];
		if(!res[node]){
			cout << "?" << endl;
			continue;
		}
		cout << "K" << res[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: 0 / 10
• Subtask 4: 0 / 40