| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 395584 | idk321 | Toy Train (IOI17_train) | C++11 | 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 "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5000;
set<int> adj[N];
vector<int> a;
vector<int> r;
vector<int> u;
vector<int> v;
bool ignore[N];
int in[N];
int up[N];
int ctime = 0;
bool goodA[N];
bool goodB[N];
vector<int> comps;
vector<int> st;
bool onSt[N];
void dfs(int node)
{
ctime++;
in[node] = ctime;
st.push_back(node);
onSt[node] = true;
for (int next : adj[node])
{
if (ignore[next]) continue;
if (next == node && r[node])
{
goodA[node] = true;
}
if (next == node) goodB[node] = true;
if (in[next] == 0)
{
dfs(next);
up[node] = min(up[node], up[next]);
} else if (onSt[next])
{
up[node] = min(up[node], in[next]);
}
}
if (in[node] == up[node])
{
vector<int> comp;
while (st.back() != node)
{
onSt[st.back()] = false;
if (r[st.back()]) goodA[st.back()] = true;
goodB[st.back()] = true;
comp.push_back(st.back());
st.pop_back();
}
comp.push_back(node);
st.pop_back();
onSt[node] = false;
if (comp.size() > 1 && r[node])
{
goodA[node] = true;
}
if (comp.size() > 1) goodB[node] = true;
}
}
bool vis[N];
bool reachGoodA(int node)
{
if (goodA[node]) return true;
vis[node] = true;
bool ok = false;
for (int next : adj[node])
{
if (vis[next]) continue;
ok = ok || reachGoodA(next);
}
return ok;
}
bool reachGoodB(int node)
{
if (goodB[node]) return true;
vis[node] = true;
bool ok = false;
for (int next : adj[node])
{
if (vis[next]) continue;
ok = ok || reachGoodB(next);
}
return ok;
}
std::vector<int> who_wins(std::vector<int> A, std::vector<int> R, std::vector<int> U, std::vector<int> V) {
a = A;
r = R;
u = U;
v = V;
int n = a.size();
int m = u.size();
bool simple = true;
for (int i = 0; i < m; i++)
{
if (!(v[i] == u[i] || v[i] == u[i] + 1)) simple = false;
adj[u[i]].insert(v[i]);
}
std::vector<int> res(a.size());
bool allA = true;
bool allB = true;
for (int i = 0; i < n; i++)
{
if (a[i] == 1) allB = false;
if (a[i] == 0) allA = false;
}
//cout << simple << endl;
if (simple)
{
for (int i = 0; i < n; i++)
{
int cur = i;
bool good = false;
int travelled = 0;
while (travelled < n)
{
if (a[cur] == 1)
{
if (r[cur] == 1)
{
if (adj[cur].find(cur) != adj[cur].end())
{
good = true;
break;
}
}
for (int next : adj[cur])
{
if (next != cur)
{
cur = next;
break;
}
}
} else
{
if (r[cur] != 1)
{
if (adj[cur].find(cur) != adj[cur].end())
{
break;
}
}
for (int next : adj[cur])
{
if (next != cur)
{
cur = next;
break;
}
}
}
travelled++;
}
if (r[cur]) good = true;
res[i] = good;
}
return res;
} else if (allA)
{
for (int i = 0; i < n; i++)
{
if (!in[i]) dfs(i);
}
for (int i = 0; i < n; i++) res[i] = reachGoodA(i);
return res;
} else if (allB)
{
for (int i = 0; i < n; i++) if (r[i]) ignore[i] = true;
for (int i = 0; i < n; i++)
{
if (!ignore[i] && !in[i]) dfs(i);
}
for (int i = 0; i < n; i++) res[i] = reachGoodB(i);
return res;
}
return res;
}