# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
752305 | definitelynotmee | Toy Train (IOI17_train) | C++17 | 479 ms | 1364 KiB |
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 "train.h"
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
using namespace std;
template <typename T>
using bstring = basic_string<T>;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 998244353;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
const int MAXN = 1e6+1;
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
int n = a.size();
vector<bstring<int>> g(n), rev(n);
for(int i = 0; i < u.size(); i++){
g[u[i]].push_back(v[i]);
rev[v[i]].push_back(u[i]);
}
vector<int> resp(n,1);
auto topo_sort=[&]{
vector<int> degree(n);
vector<int> reach(n);
vector<int> st;
for(int i = 0; i < n; i++){
if(!resp[i])
continue;
if(a[i]){
for(int j : g[i]){
if(resp[j] && r[j]){
st.push_back(i);
degree[i] = -1;
break;
}
}
} else {
for(int j : g[i]){
degree[i]+=!(resp[j] && r[j]);
}
if(degree[i] == 0)
st.push_back(i);
}
}
while(!st.empty()){
int cur = st.back();
st.pop_back();
reach[cur] = 1;
for(int i : rev[cur]){
if(!resp[i])
continue;
if(a[i]){
degree[i]--;
if(degree[i] == -1){
st.push_back(i);
}
} else {
if(!r[cur]){
degree[i]--;
if(degree[i] == 0){
st.push_back(i);
}
}
}
}
}
bool ret = 0;
for(int i = 0; i < n; i++){
ret|=reach[i]^resp[i];
resp[i]=reach[i];
}
return ret;
};
while(topo_sort()){}
return resp;
}
Compilation message (stderr)
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |