제출 #1143093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143093		PlayVoltz	KOVANICE (COI15_kovanice)	C++20	50 / 100	2097 ms	22896 KiB

kovanice

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n, m, v;
vector<int> dsu, ans, mx;
vector<vector<int> > graph;

int fp(int a){
	if (dsu[a]==-1)return a;
	return dsu[a]=fp(dsu[a]);
}

void merge(int a, int b){
	a=fp(a), b=fp(b);
	if (a!=b)dsu[a]=b;
}

void dfs(int node, int d){
	//if (mx[node])return;
	mx[node]=d;
	for (auto num:graph[node])dfs(num, d+1), mx[node]=max(mx[node], mx[num]);
	if (mx[node]==n)ans[node]=d;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int a, b;
	char c;
	cin>>n>>m>>v;
	dsu.resize(m+1, -1);
	graph.resize(m+1);
	ans.resize(m+1, -1);
	mx.resize(m+1, 0);
	vector<pii> temp;
	while (v--){
		cin>>a>>c>>b;
		if (c=='=')merge(a, b);
		else temp.pb(mp(a, b));
	}
	vector<bool> source(m+1, 1);
	for (auto a:temp)graph[fp(a.fi)].pb(fp(a.se)), source[fp(a.se)]=0;
	for (int i=1; i<=m; ++i)dfs(i, 1);
	//for (int i=1; i<=m; ++i)if (dsu[i]==-1&&source[i])dfs(i, 1);
	for (int i=1; i<=m; ++i){
		if (ans[fp(i)]==-1)cout<<"?\n";
		else cout<<"K"<<ans[fp(i)]<<"\n";
	}
}

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