Submission #846313

# Submission time Handle Problem Language Result Execution time Memory
846313 2023-09-07T13:25:02 Z vjudge1 KOVANICE (COI15_kovanice) C++11
0 / 100
90 ms 3152 KB
#include <bits/stdc++.h>
#define lg(a) (31 - __builtin_clz((a)))
#define endl ("\n")
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define vi vector<int>
#define st first
#define nd second
#define all(aa) aa.begin(), aa.end()
#define rall(aa) aa.rbegin(), aa.rend()
#define until(n, v) (int) (lower_bound(v.begin(), v.end(), n)-v.begin()) //# of elements < n
#define after(n, v) (int) (v.end()-upper_bound(v.begin(), v.end(), n))   //# of elements > n
#define sameas(n, v) (int) (upper_bound(v.begin(), v.end(), n) - lower_bound(v.begin(), v.end(), n)) //# of elements ==n
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++){
		string s; cin >> s;
		if(s[1]=='='){
			eq.insert({s[0]-'0', s[2]-'0'});
		}
		if(s[1]=='<'){
			gr.insert({s[0]-'0', s[2]-'0'});
		}
	}


	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<int> ans(m+1, 0);
	for(auto [smol , large] : gr){
		ans[topparent(smol)] = 1;
		ans[topparent(large)] = 2;
	}
	for(int i=1;i<=m;i++){
		if(ans[topparent(i)]==0){
			cout<<'?'<<endl;
		} else{
			cout<<'K'<<ans[topparent(i)]<<endl;
		}
	}

}

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



Compilation message

kovanice.cpp: In function 'void solve()':
kovanice.cpp:52:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |  for(auto [num1, num2] : eq) {
      |           ^
kovanice.cpp:61:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |  for(auto [smol , large] : gr){
      |           ^
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 3152 KB Output isn't correct
2 Halted 0 ms 0 KB -