// Ali
// #pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 3e5+23, inf = 2e9, LG = 19,pr = 31;
int val[sze];
vector<int> graph[sze];
vector<int> path;
int used[sze];
bool ff=true;
void dfs(int node){
if(used[node] || !ff){
ff=false;
return;
}
used[node]=1;
path.pb(node);
for(auto v:graph[node]){
dfs(v);
}
}
struct lan{
vector<int> parent;
vector<int> sz;
lan(int n){
parent.resize(n+23);
iota(all(parent),0);
sz.resize(n+23,1);
}
int root(int a){
if(parent[a]==a){
return a;
}
return parent[a]=root(parent[a]);
}
void unite(int a,int b){
int x = root(a);
int y = root(b);
if(x!=y){
if(sz[x]<sz[y]){
swap(x,y);
}
sz[x]+=sz[y];
parent[y]=x;
}
}
};
void fast(){
int n,m,qq;
cin>>n>>m>>qq;
vector<pair<pii,char>> q;
bool flag=false;
while(qq--){
string s;
cin>>s;
string a="";
string b="";
char op;
for(auto v:s){
if(v=='<' || v=='='){
op = v;
swap(a,b);
}
else{
a+=v;
}
}
swap(a,b);
q.pb({{stoll(a),stoll(b)},op});
// cout<<a<<" "<<op<<" "<<b<<endl;
if(op=='<' && !flag){
flag=true;
}
}
lan dsu(m+23);
if(flag){
vector<int> fk(m+23,0);
set<int> lst;
vector<pair<int,int>> fuk;
for(auto [vv,op]:q){
int a = vv.first;
int b = vv.second;
if(op=='='){
dsu.unite(a,b);
}
else{
// val[a]=1;
// val[b]=2;
// a<b ise ne olucak ?
// en boyuk hansidi o lazim
fuk.pb({a,b});
lst.ins(a);
lst.ins(b);
}
}
set<pair<int,int>> gg;
for(auto [k,v]:fuk){
int a = dsu.root(k);
if(a!=k && lst.find(k)!=lst.end()){
lst.erase(k);
}
int b = dsu.root(v);
if(b!=v && lst.find(v)!=lst.end()){
lst.erase(v);
}
// cout<<a<<" "<<b<<endl;
if(gg.find({b,a})==gg.end()){
gg.ins({b,a});
graph[b].pb(a);
}
}
for(auto v:fuk){
int a = dsu.root(v.first);
// cout<<v.first<<" ,"<<v.second<<endl;
if(lst.find(a)!=lst.end()){
lst.erase(lst.find(a));
}
}
// for(auto v:lst){
// cout<<v<<" ";
// }cout<<endl;
if(lst.size()==1){
int a = *lst.begin();
// cout<<"enbuyuk : "<<a<<endl;
dfs(a);
// cout<<ff<<endl;
// for(auto v:path) cout<<v<<" ";cout<<endl;
if((path.size()==n)){
int x =n;
for(auto v:path){
assert(x>0);
val[v]=(x--);
}
}
}
for(int i =1;i<=m;i++){
fk[dsu.root(i)]|=val[i];
}
for(int i =1;i<=m;i++){
val[i]=fk[dsu.root(i)];
}
}
for(int i=1;i<=m;i++){
if(val[i]<=0){
cout<<"?"<<endl;
}
else{
cout<<"K"<<val[i]<<endl;
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt = 1;
// cin>>tt;
while(tt--){
fast();
}
return 0;
}
Compilation message
kovanice.cpp: In function 'void fast()':
kovanice.cpp:137:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
137 | if((path.size()==n)){
| ~~~~~~~~~~~^~~
kovanice.cpp:80:9: warning: 'op' may be used uninitialized in this function [-Wmaybe-uninitialized]
80 | if(op=='<' && !flag){
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
7696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
173 ms |
25712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
13312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
636 ms |
49952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
