| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 789618 | esomer | Toy Train (IOI17_train) | C++17 | 0 ms | 0 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<bits/stdc++.h>
#include "train.h"
using namespace std;
typedef long long ll;
//~ vector<int> who_wins2(vector<int> A, vector<int> R, vector<int> U, vector<int> V){
//~ int n = (int)A.size();
//~ int m = (int)U.size();
//~ bool first = 1;
//~ for(int i = 0; i < m; i++){
//~ if(V[i] != U[i] && V[i] != U[i] + 1) first = 0;
//~ }
//~ if(first){
//~ vector<bool> self(n, 0);
//~ vector<bool> other(n, 0);
//~ for(int i = 0; i < m; i++){
//~ if(U[i] == V[i]) self[U[i]] = 1;
//~ else other[U[i]] = 1;
//~ }
//~ vector<int> ans(n, 0);
//~ for(int i = n - 1; i >= 0; i--){
//~ if(A[i] == 1){
//~ if(self[i] == 1 && R[i] == 1) ans[i] = 1;
//~ else if(other[i] == 1) ans[i] = ans[i+1];
//~ }else{
//~ if(self[i] == 1){
//~ if(R[i] == 0) ans[i] = 0;
//~ else{
//~ if(other[i]) ans[i] = ans[i+1];
//~ else ans[i] = 1;
//~ }
//~ }else if(other[i] == 1) ans[i] = ans[i+1];
//~ }
//~ }
//~ return ans;
//~ }else return {};
//~ }
void process(vector<int>& A, vector<int>& R, vector<int>& U, vector<int>& V, vector<bool>& forced){
int n = (int)A.size();
int m = (int)U.size();
vector<vector<int>> radj(n);
vector<int> out(n, 0);
for(int i = 0; i < m; i++){
if(R[U[i]] == 1) continue;
out[U[i]]++;
radj[V[i]].push_back(U[i]);
}
queue<int> q;
for(int i = 0; i < n; i++){
if(out[i] == 0){
forced[i] = 0;
q.push(i);
}
}
while(!q.empty()){
int x = q.front(); q.pop();
for(int node : radj[x]){
out[node]--;
if(out[node] == 0 && forced[node] == 1) {q.push(node); forced[node] = 0;}
if(A[node] == 1 && forced[node] == 1){
forced[node] = 0;
q.push(node);
}
}
}
radj.assign(n, {});
out.assign(n, 0);
for(int i = 0; i < m; i++){
if(forced[U[i]] == 1) continue;
out[U[i]]++;
radj[V[i]].push_back(U[i]);
}
for(int i = 0; i < n; i++){
if(out[i] == 0){
q.push(i);
}
}
while(!q.empty()){
int x = q.front(); q.pop();
for(int node : radj[x]){
out[node]--;
if(out[node] == 0 && forced[node] == 0) {q.push(node); forced[node] = 1;}
if(A[node] == 0 && forced[node] == 0){
forced[node] = 1;
q.push(node);
}
}
}
}
vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V){
int n = (int)A.size();
int m = (int)U.size();
bool stop = 0;
vector<bool> forced; //If 1, then it can be forced by B into a cycle with no R's.
while(!stop){
stop = 1;
forced.assign(n, 1);
process(A, R, U, V, forced);
for(int i = 0; i < n; i++){
if(forced[i] == 1 && R[i] == 1) {R[i] = 0; stop = 0;}
}
}
vector<int> ans(n);
for(int i = 0; i < n; i++){
if(forced[i] == 1) ans[i] = 0;
else ans[i] = 1;
}
return ans;
}
mt19937 gen(time(0));
void generate(){
for(int tt = 0; tt <= 10000; tt++){
int n = gen() % 5 + 1;
int m = gen() % 5 + n;
vector<int> a(n), r(n), u(m), v(m);
for(int i = 0; i < n; i++)
a[i] = gen() % 2;
for(int i = 0; i < n; i++)
r[i] = gen() % 2;
for(int i = 0; i < n; i++){
u[i] = i;
if(u[i] == n - 1) v[i] = u[i];
else v[i] = u[i] + gen() % 2;
}
for(int i = n; i < m; i++){
u[i] = gen() % n;
if(u[i] == n - 1) v[i] = u[i];
else v[i] = u[i] + gen() % 2;
}
vector<int> res = who_wins(a, r, u, v);
vector<int> res2 = who_wins2(a, r, u, v);
if(res != res2){
cout << n << " " << m << endl;
for(int x : a) cout << x << " ";
cout << endl;
for(int x : r) cout << x << " "; cout << endl;
for(int i = 0; i < m; i++){
cout << u[i] << " " << v[i] << endl;
}
cout << "RES: ";
for(int x : res) cout << x << " "; cout << endl;
cout << "RES2: ";
for(int x : res2) cout << x << " "; cout << endl;
return;
}
}
}
//~ int main() {
//~ generate(); return 0;
freopen("in.txt", "r", stdin);
//~ int n, m;
//~ assert(2 == scanf("%d %d", &n, &m));
//~ vector<int> a(n), r(n), u(m), v(m);
//~ for(int i = 0; i < n; i++)
//~ assert(1 == scanf("%d", &a[i]));
//~ for(int i = 0; i < n; i++)
//~ assert(1 == scanf("%d", &r[i]));
//~ for(int i = 0; i < m; i++)
//~ assert(2 == scanf("%d %d", &u[i], &v[i]));
//~ vector<int> res = who_wins(a, r, u, v);
//~ for(int i = 0; i < (int)res.size(); i++)
//~ printf(i ? " %d" : "%d", res[i]);
//~ printf("\n");
//~ return 0;
//~ }