Submission #846310

#	Time	Username	Problem	Language	Result	Execution time	Memory
846310		vjudge1	KOVANICE (COI15_kovanice)	C++17	100 / 100	677 ms	40368 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define tol(bi) (1LL<<((int)(bi)))
int32_t main(){
	int m,n,v;
	cin>>m>>n>>v;
	vector<int> par(n);
	iota(par.begin(), par.end(), 0);
	function<int(int)> fp;fp = [&](int node){
		if (par[node]==node) return node;
		return par[node]=fp(par[node]);
	};
	vector<array<int,2>> seq;
	for (int i = 0; i < v; i++){
		string str;
		cin>>str;
		int a=0, b=0;
		char chr;
		int hehe = 1;
		while (str.size() && str.back()!='<' && str.back()!='>' && str.back()!='='){
			b+=(str.back()-'0')*hehe;
			hehe*=10;
			str.pop_back();
		}
		chr=str.back();
		str.pop_back();
		hehe=1;
		while (str.size()){
			a+=(str.back()-'0')*hehe;
			hehe*=10;
			str.pop_back();
		}
		if (chr=='='){
			par[fp(a-1)]=fp(b-1);
		}
		else {
			if (chr=='>'){
				seq.push_back({a-1,b-1});
			}
			else seq.push_back({b-1,a-1});
		}
	}
	vector<vector<int>> arr(n);
	vector<vector<int>> barr(n);
	vector<bool> _vis(n,true);
	for (int i = 0; i < seq.size(); i++){
		int u = fp(seq[i][0]);
		int v = fp(seq[i][1]);
		_vis[u]=_vis[v]=false;
		arr[u].push_back(v);
		barr[v].push_back(u);
	}
	vector<bool> vis=_vis;
	vector<int> ust(n,0);
	vector<int> alt(n,0);
	function<void(int)> dfs;dfs = [&](int node){
		if (vis[node]) return;
		vis[node]=true;
		ust[node]=0;
		for (int i = 0; i < arr[node].size(); i++){
			dfs(arr[node][i]);
			ust[node]=max(ust[node],ust[arr[node][i]]+1);
		}
	};
	for (int i = 0; i < n; i++){
		if (!vis[i]) dfs(i);
	}
	vis=_vis;
	dfs=[&](int node){
		if (vis[node]) return;
		vis[node]=true;
		alt[node]=0;
		for (int i = 0; i < barr[node].size(); i++){
			dfs(barr[node][i]);
			alt[node]=max(alt[node],alt[barr[node][i]]+1);
		}
	};
	for (int i = 0; i < n; i++){
		if (!vis[i]) dfs(i);
	}
	for (int i = 0; i < n; i++){
		int node = fp(i);
		if (ust[node]+alt[node]+1==m){
			cout<<"K"<<ust[node]+1<<endl;
		}
		else cout<<"?"<<endl;
	}
}

Compilation message (stderr)

kovanice.cpp: In function 'int32_t main()':
kovanice.cpp:47:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (int i = 0; i < seq.size(); i++){
      |                  ~~^~~~~~~~~~~~
kovanice.cpp: In lambda function:
kovanice.cpp:61:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
kovanice.cpp: In lambda function:
kovanice.cpp:74:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for (int i = 0; i < barr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~

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