#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++){
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<int> ans(m+1, 0);
for(auto [smol , large] : gr){
ans[topparent(smol)] = 1;
ans[topparent(large)] = 2;
// cout<<smol<<' '<<large<<endl;
}
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:53:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
53 | for(auto [num1, num2] : eq) {
| ^
kovanice.cpp:63:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
63 | for(auto [smol , large] : gr){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
7224 KB |
Output is correct |
| 2 |
Correct |
86 ms |
7116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
2896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
304 ms |
17444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
