This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int n,m,v1,d[300005],cnt[300005],bio[300005];
vector <int> v[300005],eq[300005];
int dfs(int x,int d1) {
int ret=d1;
for(int i=0;i<v[x].size();i++) {
ret=max(ret,dfs(v[x][i],d1+1));
}
if(ret==n) d[x]=d1;
return ret;
}
void dfs2(int x,int a) {
d[x]=a;
bio[x]=1;
for(int i=0;i<eq[x].size();i++) {
if(bio[eq[x][i]]) continue;
dfs2(eq[x][i],a);
}
}
int main()
{
cin >> n >> m >> v1;
for(int i=0;i<v1;i++) {
string s;
cin >> s;
int ind=0,a=0,b=0;
while(s[ind]>='0' && s[ind]<='9') {
a*=10;
a+=s[ind]-'0';
ind+=1;
}
for(int j=ind+1;j<s.size();j++) {
b*=10;
b+=s[j]-'0';
}
if(s[ind]=='=') {
eq[a-1].push_back(b-1);
eq[b-1].push_back(a-1);
}
else if(s[ind]=='<') {
v[a-1].push_back(b-1);
cnt[b-1]+=1;
}
else {
v[b-1].push_back(a-1);
cnt[a-1]+=1;
}
}
for(int i=0;i<m;i++) {
if(cnt[i]==0) dfs(i,1);
}
for(int i=0;i<m;i++) {
if(d[i] && bio[i]==0) dfs2(i,d[i]);
}
for(int i=0;i<m;i++) {
if(d[i]) cout << "K" << d[i] << "\n";
else cout << "?\n";
}
return 0;
}
Compilation message (stderr)
kovanice.cpp: In function 'int dfs(int, int)':
kovanice.cpp:10:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++) {
~^~~~~~~~~~~~
kovanice.cpp: In function 'void dfs2(int, int)':
kovanice.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<eq[x].size();i++) {
~^~~~~~~~~~~~~
kovanice.cpp: In function 'int main()':
kovanice.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=ind+1;j<s.size();j++) {
~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |