Submission #1143096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143096		PlayVoltz	KOVANICE (COI15_kovanice)	C++20	60 / 100	112 ms	34288 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, mx, depth;
vector<vector<int> > graph, tgraph;

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;
}

int dfs(int node){
	if (depth[node])return depth[node];
	depth[node]=1;
	for (auto num:graph[node])depth[node]=max(depth[node], dfs(num)+1);
	return depth[node];
}

int dfs2(int node){
	if (mx[node])return mx[node];
	mx[node]=depth[node];
	for (auto num:tgraph[node])mx[node]=max(mx[node], dfs2(num));
	return mx[node];
}

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);
	tgraph.resize(m+1);
	mx.resize(m+1, 0);
	depth.resize(m+1, 0);
	vector<pii> temp;
	while (v--){
		cin>>a>>c>>b;
		if (c=='=')merge(a, b);
		else temp.pb(mp(a, b));
	}
	for (auto a:temp)graph[fp(a.fi)].pb(fp(a.se)), tgraph[fp(a.se)].pb(fp(a.fi));
	for (int i=1; i<=m; ++i)if (dsu[i]==-1&&!depth[i])dfs(i);
	for (int i=1; i<=m; ++i)if (dsu[i]==-1&&!mx[i])dfs2(i);
	for (int i=1; i<=m; ++i){
		if (mx[fp(i)]==n)cout<<"K"<<n-depth[fp(i)]+1<<"\n";
		else cout<<"?\n";
	}
}

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