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;
const int N = 3e5 + 5;
int n, m, k, p[N], dp1[N], dp2[N], used[N], sz;
vector < int > g[N], gr[N], q[N];
vector < pair < int, int > > e;
void dfs(int v){
used[v] = sz;
for(int to : q[v]){
if(!used[to]){
dfs(to);
}
}
}
int dfs1(int v){
if(dp1[v]){
return dp1[v];
}
for(int to : g[v]){
dp1[v] = max(dp1[v], dfs1(to));
}
dp1[v] += 1;
return dp1[v];
}
int dfs2(int v){
if(dp2[v]){
return dp2[v];
}
for(int to : gr[v]){
dp2[v] = max(dp2[v], dfs2(to));
}
dp2[v] += 1;
return dp2[v];
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m >> k;
for(int i = 1; i <= k; i++){
int x, y;
char c;
cin >> x >> c >> y;
if(c == '<'){
e.push_back(make_pair(x, y));
}
else{
q[x].push_back(y);
q[y].push_back(x);
}
}
for(int i = 1; i <= m; i++){
if(!used[i]){
sz += 1;
dfs(i);
}
}
for(auto it : e){
g[used[it.second]].push_back(used[it.first]);
gr[used[it.first]].push_back(used[it.second]);
}
for(int i = 1; i <= m; i++){
dfs1(used[i]);
dfs2(used[i]);
}
for(int i = 1; i <= m; i++){
if(dp1[used[i]] + dp2[used[i]] - 1 == n){
cout << "K" << dp1[used[i]] << "\n";
}
else{
cout << "?\n";
}
}
}
# | 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... |