| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 395608 |
2021-04-28T16:43:24 Z |
idk321 |
Toy Train (IOI17_train) |
C++11 |
|
83 ms |
2556 KB |
#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 miss[N];
int in[N];
int up[N];
int timer = 0;
bool goodA[N];
bool goodB[N];
vector<int> comps;
vector<int> st;
bool onSt[N];
void dfs(int node)
{
timer++;
in[node] = timer;
up[node] = in[node];
st.push_back(node);
onSt[node] = true;
for (int next : adj[node])
{
if (miss[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;
bool aGood = false;
bool bGood = false;
while (st.back() != node)
{
onSt[st.back()] = false;
if (r[st.back()]) aGood = true;
bGood = 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])
{
aGood = true;
}
if (comp.size() > 1) bGood = true;
if (aGood)
{
for (int i : comp) goodA[i] = true;
}
if (bGood) for (int i : comp) goodB[i] = 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]) miss[i] = true;
for (int i = 0; i < n; i++)
{
if (!miss[i] && !in[i]) dfs(i);
}
for (int i = 0; i < n; i++) res[i] = reachGoodB(i);
return res;
}
return res;
}
/*
10 12
1 1 1 1 1 1 1 1 1 1
0 0 1 0 0 0 1 0 0 0
0 1
1 2
2 1
1 3
1 4
4 5
5 4
6 6
7 7
3 3
8 9
9 8
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1152 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 4 |
Correct |
7 ms |
1100 KB |
Output is correct |
| 5 |
Correct |
13 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
24 ms |
1100 KB |
Output is correct |
| 7 |
Correct |
26 ms |
1100 KB |
Output is correct |
| 8 |
Correct |
22 ms |
1100 KB |
Output is correct |
| 9 |
Correct |
49 ms |
1104 KB |
Output is correct |
| 10 |
Correct |
68 ms |
1080 KB |
Output is correct |
| 11 |
Correct |
83 ms |
1028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
460 KB |
3rd lines differ - on the 2nd token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
2508 KB |
Output is correct |
| 2 |
Correct |
11 ms |
2400 KB |
Output is correct |
| 3 |
Correct |
10 ms |
2508 KB |
Output is correct |
| 4 |
Correct |
10 ms |
2556 KB |
Output is correct |
| 5 |
Correct |
10 ms |
2380 KB |
Output is correct |
| 6 |
Correct |
11 ms |
2124 KB |
Output is correct |
| 7 |
Correct |
10 ms |
2124 KB |
Output is correct |
| 8 |
Incorrect |
13 ms |
2124 KB |
3rd lines differ - on the 79th token, expected: '1', found: '0' |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
1788 KB |
3rd lines differ - on the 1st token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
2016 KB |
3rd lines differ - on the 1st token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1152 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 4 |
Correct |
7 ms |
1100 KB |
Output is correct |
| 5 |
Correct |
13 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
24 ms |
1100 KB |
Output is correct |
| 7 |
Correct |
26 ms |
1100 KB |
Output is correct |
| 8 |
Correct |
22 ms |
1100 KB |
Output is correct |
| 9 |
Correct |
49 ms |
1104 KB |
Output is correct |
| 10 |
Correct |
68 ms |
1080 KB |
Output is correct |
| 11 |
Correct |
83 ms |
1028 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
460 KB |
3rd lines differ - on the 2nd token, expected: '1', found: '0' |
| 13 |
Halted |
0 ms |
0 KB |
- |
