Submission #846606

#	Time	Username	Problem	Language	Result	Execution time	Memory
846606		vjudge1	KOVANICE (COI15_kovanice)	C++11	0 / 100	737 ms	43856 KiB

kovanice

#include <bits/stdc++.h>
// #define endl ("\n")
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define st first
#define nd second
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
const ll MOD = 1e9+7;
using namespace std;
/*

*/

vector<int> parent;
int topparent(int par) {
	if(parent[par]==par) return par; // if it is its own parent then it is the topparent
	return (parent[par] = topparent(parent[par])); // check the parents parents for topparent, set the parent as topparent
}


void solve(){
	int n, m, v; cin>>n>>m>>v;

	set<pair<int, int>> eq;
	set<pair<int, int>> gr;
	for(int i=0;i<v;i++){
		int a; cin>>a;
		char c; cin>>c;
		int b; cin >> b;
		if(c=='='){
			eq.insert({a, b});
		}
		if(c=='<'){
			gr.insert({a, b});
		}
	}

	parent.resize(m+1); // represent equal terms by one value
	for(int i=1;i<=m;i++){
		parent[i] = i;
	}

	for(auto [num1, num2] : eq)	{
		parent[topparent(num1)] = topparent(num2);
	}
	// we have compressed all equalities to only distinct values


	// for n=2
	// store the value of the topparents

	vector<vector<int>> in(m+1);
	vector<vector<int>> out(m+1);
	vector<array<int, 2>> dp(m+1);
	vector<array<int, 2>> used(m+1);
	for(auto [smol , large] : gr){
		out[topparent(large)].pb(topparent(smol));
		in[topparent(smol)].pb(topparent(large));
	}

	function<int(int, int)> dfs = [&](int u, int type){
		// cout<<"ENTERED DFS FOR: "<<u<<' '<<type<<' '<<dp[u][type]<<endl;
		if(type==1 and out[u].size()==0) return dp[u][1] = 0;
		if(type==0 and in[u].size()==0) return dp[u][0] = 0;

		if(used[u][type]) 
			return dp[u][type];
		if(type==1){
			used[u][1] = 1;
			for(auto v:out[u]){
				dp[u][1] = max(dp[u][1], dfs(v, 1)+1);
			}
		}
		else{
			used[u][0] = 1;
			for(auto v: in[u]){
				dp[u][0] = max(dp[u][0], dfs(v, 0)+1);
			}
		}
		return dp[u][type];
	};

	for(int i=1;i<=m;i++){
		if(in[i].size()==0){
			dfs(topparent(i), 1);
		}
		if(out[i].size()==0){
			dfs(topparent(i), 0);
		}
	}

	for(int i=1;i<=m;i++){
		if(dp[topparent(i)][0] + dp[topparent(i)][1]==n-1){
			cout<<'K'<<dp[topparent(i)][0]+1<<endl;
		} else{
			cout<<'?'<<endl;
		}
	}




}

int main(){
	int test; 
    // cin >> test;
    test =1;
   	while (test--){
		solve();
    }
}

Compilation message (stderr)

kovanice.cpp: In function 'void solve()':
kovanice.cpp:45:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |  for(auto [num1, num2] : eq) {
      |           ^
kovanice.cpp:58:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |  for(auto [smol , large] : gr){
      |           ^

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