#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)][1]+1<<endl;
} else{
cout<<'?'<<endl;
}
}
}
int main(){
int test;
// cin >> test;
test =1;
while (test--){
solve();
}
}
Compilation message
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){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
604 KB |
Output is correct |
| 2 |
Correct |
3 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
336 ms |
21248 KB |
Output is correct |
| 2 |
Correct |
337 ms |
21620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
3380 KB |
Output is correct |
| 2 |
Correct |
58 ms |
3156 KB |
Output is correct |
| 3 |
Correct |
55 ms |
2896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
758 ms |
43280 KB |
Output is correct |
| 2 |
Correct |
751 ms |
42472 KB |
Output is correct |
| 3 |
Correct |
723 ms |
42368 KB |
Output is correct |
| 4 |
Correct |
769 ms |
46320 KB |
Output is correct |
| 5 |
Correct |
799 ms |
46408 KB |
Output is correct |
