oj.uz

Submission #846310

# Submission time Handle Problem Language Result Execution time Memory
846310 2023-09-07T13:22:33 Z vjudge1 KOVANICE (COI15_kovanice) C++17
100 / 100
 677 ms 40368 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 18768 KB Output is correct
2 Correct 283 ms 18764 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4040 KB Output is correct
2 Correct 27 ms 4036 KB Output is correct
3 Correct 30 ms 4040 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 34516 KB Output is correct
2 Correct 616 ms 34256 KB Output is correct
3 Correct 567 ms 33464 KB Output is correct
4 Correct 637 ms 39600 KB Output is correct
5 Correct 677 ms 40368 KB Output is correct