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;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
vector<vector<int>> edges;
vector<vector<int>> redges;
vector<int> minreach;
vector<int> maxreturn;
int n,k;
void init(int N,int K){
n=N;
k=K;
for(int i=0;i<n;i++){
edges.push_back({});
redges.push_back({});
}
for(int i=0;i<k;i++){
minreach.push_back(i);
maxreturn.push_back(i);
}
for(int i=k;i<n;i++){
minreach.push_back(k);
maxreturn.push_back(-1);
}
}
bool dfs(int u){
bool ans=true;
if((maxreturn[u]>minreach[u]) || (maxreturn[u]==minreach[u] && u>=k)) ans=false;
for(int v:edges[u]){
if(maxreturn[v]<maxreturn[u]){
maxreturn[v]=maxreturn[u];
if(!dfs(v)) ans=false;;
}
}
return ans;
}
bool rdfs(int u){
bool ans=true;
if((maxreturn[u]>minreach[u]) || (maxreturn[u]==minreach[u] && u>=k)) ans=false;
for(int v:redges[u]){
if(minreach[v]>minreach[u]){
minreach[v]=minreach[u];
if(!dfs(v)) ans=false;;
}
}
return ans;
}
int add_teleporter(int u,int v){
if(u==v){
if(u>=k) return 0;
return 1;
}
edges[u].push_back(v);
redges[v].push_back(u);
if(maxreturn[v]<maxreturn[u]){
maxreturn[v]=maxreturn[u];
if(!dfs(v)) return 1;
}
if(minreach[u]>minreach[v]){
minreach[u]=minreach[v];
if(!rdfs(u)) return 1;
}
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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |