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>adj[N],temp[N];
bool ok = 1;
int dp[N];
int dfs(int node){
if(dp[node] != -1){
return dp[node];
}
if(adj[node].empty() && used==0){
st.erase(st.find(1));
used = 1;
return dp[node]=1;
}
else if(adj[node].empty()){
return dp[node]=0;
}
int mx = 0;
for(int child : adj[node]){
int res = dfs(child);
if(!res){
return dp[node]=0;
}
mx = max(mx, res);
}
auto it = st.upper_bound(mx);
if(it == st.end()){
ok=0;
return dp[node]=0;
}
int val = *it;
st.erase(it);
return dp[node] = val;
}
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(dp,-1,sizeof(dp));
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[rec(a)]=f[rec(b)];
}
else{
temp[b].push_back(a);
}
}
int hasparent[m+1]{};
for(int i = 1; i <= m; i++)rec(i);
for(int i = 1; i <= m; i++){
for(int child : temp[i]){
adj[f[i]].push_back(f[child]);
hasparent[f[child]]=1;
}
}
for(int i = 1; i <= n; i++){
st.insert(i);
}
vector<int>vec;
for(int i = 1; i <= m; i++){
vec.push_back(dfs(f[i]));
}
for(int i : vec){
if(i == 0)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... |