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 <bits/stdc++.h>
using namespace std;
using ll = int64_t;
const int N = 3e5 + 3;
bool used=0;
set<int>st;
vector<int>adj1[N],adj2[N],temp[N];
bool ok = 1;
int dp1[N],dp2[N];
int dfs1(int node){
if(dp1[node]!=-1)
return dp1[node];
int ret = 1;
for(int child : adj1[node]){
ret=max(ret, dfs1(child) + 1);
}
return dp1[node]=ret;
}
int dfs2(int node){
if(dp2[node]!=-1)
return dp2[node];
int ret = 1;
for(int child:adj2[node]){
ret=max(ret, dfs2(child) + 1);
}
return dp2[node]=ret;
}
int f[N];
int rec(int i){
if(f[i]==i)return i;
return f[i]=rec(f[i]);
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m,v;
cin>>n>>m>>v;
memset(dp1,-1,sizeof(dp1));
memset(dp2,-1,sizeof(dp2));
for(int i = 1; i <= m; i++){
f[i]=i;
}
for(int i = 0; i < v; i++){
string s;
cin>>s;
int j = 0;
int a = 0, b = 0;
bool l = 0, eq = 0;
while(j != int(s.size())){
if(s[j]=='<'){
l=1;
++j;
continue;
}
if(s[j] == '='){
eq = 1,l=1;
++j;
continue;
}
if(!l)a*=10,a+=s[j]-'0';
else b*=10,b+=s[j]-'0';;
++j;
}
if(eq){
f[max(a,b)]=f[min(a,b)];
}
else{
temp[b].push_back(a);
}
}
for(int i = 1; i <= m; i++)rec(i);
for(int i = 1; i <= m; i++){
for(int child : temp[i]){
adj1[f[i]].push_back(f[child]);
adj2[f[child]].push_back(f[i]);
}
}
for(int i = 1; i <= n; i++){
st.insert(i);
}
vector<int>vec;
for(int i = 1; i <= m; i++){
if(dfs1(f[i])+dfs2(f[i]) != n+1){
vec.push_back('?');
}
else vec.push_back(dfs1(f[i]));
}
for(int i : vec){
if(i == '?')cout<<"?\n";
else cout<<'K'<<i<<'\n';
}
return 0;
}
# | 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... |