Submission #239276

#TimeUsernameProblemLanguageResultExecution timeMemory
239276lycToy Train (IOI17_train)C++14
0 / 100
2039 ms99704 KiB
#include "train.h" #include <bits/stdc++.h> using namespace std; #define TRACE(x) cout << #x << " :: " << x << endl; #define _ << " " << #define FOR(i,a,b) for(int i=(a);i<=(b);++i) #define RFOR(i,a,b) for(int i=(a);i>=(b);--i) #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(),(x).end() const int mxN = 5005; int N, M, A[mxN]; vector<int> al[mxN]; int rf[mxN], src; int f(int u) { if (~rf[u]) return rf[u]; rf[u] = -2; if (A[u]) { bool tmp = 0; for (int v : al[u]) { if (v == src) tmp |= 1; else if (rf[v] != -2) tmp |= f(v); } return rf[u] = tmp; } else { bool tmp = 1; for (int v : al[u]) { if (v == src) tmp &= 1; else if (rf[v] != -2) tmp &= f(v); } return rf[u] = tmp; } } int rg[mxN][mxN]; int g(int u, int p) { if (~rg[u][p]) return rg[u][p]; if (A[u]) { rg[u][p] = 0; for (int v : al[u]) { rg[u][p] |= g(v,p-1); } } else { rg[u][p] = 1; for (int v : al[u]) { rg[u][p] &= g(v,p-1); } } return rg[u][p]; } vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) { N = SZ(a); FOR(i,0,N-1){ A[i] = a[i]; } M = SZ(u); FOR(i,0,M-1){ al[u[i]].push_back(v[i]); } memset(rg,-1,sizeof rg); FOR(i,0,N-1){ if (r[i]) { src = i; memset(rf,-1,sizeof rf); f(src); FOR(j,0,N-1) if (rf[i] == 1) rg[i][0] = 1; } } FOR(i,0,N-1){ if (rg[i][0] == 1) { FOR(p,0,N-1) rg[i][p] = 1; } else { rg[i][0] = 0; } } vector<int> res(N); for (int i = 0; i < N; i++) { res[i] = g(i,N); } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...