#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<cstring>
using namespace std;
pair <vector <int>,vector <int> > v[300005];
int depth[300005],parent[300005],bio[300005],maxi=0,a[300005];
void dfs(int x,int par,int d) {
parent[x]=par;
depth[x]=max(depth[x],d);
bio[x]=1;
//cout <<x<<" "<<d<<endl;
maxi=max(maxi,d);
for(int i=0;i<(v[x].first).size();i++) {
if(bio[(v[x].first)[i]]==1) continue;
dfs((v[x].first)[i],x,d+1);
}
for(int i=0;i<(v[x].second).size();i++) {
if(bio[(v[x].second)[i]]==1) continue;
dfs((v[x].second)[i],parent[(v[x].second)[i]],d);
}
}
void dfs2(int x,int par,int d) {
depth[x]=-1;
//cout <<x<<endl;
for(int i=0;i<(v[x].first).size();i++) {
if(bio[(v[x].first)[i]]==1) continue;
dfs2((v[x].first)[i],x,d+1);
}
for(int i=0;i<(v[x].second).size();i++) {
if(bio[(v[x].second)[i]]==1) continue;
dfs2((v[x].second)[i],parent[(v[x].second)[i]],d);
}
}
int main()
{
int n,m,v1;
cin >> n >> m >> v1;
set <int> s1;
for(int i=0;i<m;i++) {
s1.insert(i);
depth[i]=-1;
}
for(int i=0;i<v1;i++) {
string s;
cin >> s;
int ind=0,b1=0,b2=0;
for(int j=0;j<s.size();j++) {
if(s[j]=='=' or s[j]=='<') ind=j;
}
int x=1;
for(int j=ind-1;j>=0;j--) {
b1+=(int(s[j])-48)*x;
x*=10;
}
x=1;
for(int j=s.size()-1;j>ind;j--) {
b2+=(int(s[j])-48)*x;
x*=10;
}
if(s[ind]=='=') {
(v[b1-1].second).push_back(b2-1);
(v[b2-1].second).push_back(b1-1);
}
if(s[ind]=='<') {
(v[b1-1].first).push_back(b2-1);
s1.erase(b2-1);
}
}
for(set <int>::iterator it=s1.begin();it!=s1.end();it++) {
//cout <<"s1 "<<(*it)<<endl;
if(bio[(*it)]==1) continue;
maxi=0;
dfs((*it),(*it),1);
//cout <<endl<<maxi<<endl;
if(maxi==n) a[(*it)]=1;
/*if(maxi!=n) {
cout <<"a"<<endl;
dfs2((*it),(*it),1);
}
for(int i=0;i<m;i++) {
cout <<depth[i]<<" ";
}
cout <<endl;*/
}
for(int i=0;i<m;i++) {
//cout <<a[i]<<endl;
bio[i]=0;
depth[i]=-1;
}
for(int i=0;i<m;i++) {
if(a[i]==1 && bio[i]==0) dfs(i,i,1);
}
for(int i=0;i<m;i++) {
if(depth[i]==-1) cout <<"?"<<endl;
else cout <<"K"<<depth[i]<<endl;
}
return 0;
}
/*
5 8 6
1<2
2<3
4<5
5<6
6<7
7<8
*/
Compilation message
kovanice.cpp: In function 'void dfs(int, int, int)':
kovanice.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<(v[x].first).size();i++) {
~^~~~~~~~~~~~~~~~~~~~
kovanice.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<(v[x].second).size();i++) {
~^~~~~~~~~~~~~~~~~~~~~
kovanice.cpp: In function 'void dfs2(int, int, int)':
kovanice.cpp:27:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<(v[x].first).size();i++) {
~^~~~~~~~~~~~~~~~~~~~
kovanice.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<(v[x].second).size();i++) {
~^~~~~~~~~~~~~~~~~~~~~
kovanice.cpp: In function 'int main()':
kovanice.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<s.size();j++) {
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
494 ms |
30968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
15864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1056 ms |
41688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
