#include "train.h"
//#include "grader.cpp"
#include <vector>
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int MAXN = 5005;
int n;
vector <int> adj[MAXN];
int owner[MAXN], charging[MAXN];
int guessSubtask(vector <int> a, vector <int> r, vector <int> u, vector <int> v)
{
bool sub1 = true;
for(int i = 0;i<u.size();i++)
{
if(u[i]!=v[i] && u[i]+1!=v[i])
{
sub1 = false;
break;
}
}
if(sub1==true) return 1;
bool sub3 = true;
for(int i = 0;i<a.size();i++)
{
if(a[i]!=1)
{
sub3 = false;
break;
}
}
if(sub3==true) return 3;
return -1;
}
vector <int> solve1()
{
vector <int> res(n, -1);
for(int s = 0;s<n;s++)
{
int x = s;
while(true)
{
int goal = -1;
if(owner[x]==1)
{
if(charging[x]==1) goal = x;
else goal = x + 1;
bool found = false;
for(int y: adj[x])
{
if(y==goal)
{
found =true;
break;
}
}
if(found==true)
{
if(goal==x)
{
res[s] = true;
break;
}
else
{
x = x + 1;
}
}
else
{
if(goal==x)
{
x = x + 1;
}
else
{
res[s] = false;
break;
}
}
}
else
{
if(charging[x]==1) goal = x + 1;
else goal = x;
bool found = false;
for(int y: adj[x])
{
if(y==goal)
{
found =true;
break;
}
}
if(found==true)
{
if(goal==x)
{
res[s] = false;
break;
}
else
{
x = x + 1;
}
}
else
{
if(goal==x)
{
x = x + 1;
}
else
{
res[s] = true;
break;
}
}
}
}
}
return res;
}
bool reachable[MAXN][MAXN];
vector <int> solve3()
{
vector <int> res(n, -1);
function <void(int, int, int)> dfsMark = [&](int x, int start, int depth)
{
if(depth!=0) reachable[start][x] = true;
for(int y: adj[x])
{
if(reachable[start][x]==false) dfsMark(y, start, depth+1);
}
};
for(int i = 0;i<n;i++) dfsMark(i, i, 0);
vector <int> chargingStations;
for(int i = 0;i<n;i++)
{
if(charging[i]==1) chargingStations.push_back(i);
}
vector <bool> used(n, false);
function <bool(int)> solve = [&](int x)
{
if(used[x]==true) return false;
used[x] = true;
bool ans = false;
for(int station: chargingStations)
{
if(station==x) continue;
if(reachable[x][station]==true && reachable[station][x]==true)
{
ans = true;
break;
}
}
if(charging[x]==true)
{
for(int i = 0;i<n;i++)
{
if(i==x) continue;
if(reachable[x][i]==true && reachable[i][x]==true)
{
ans = true;
break;
}
}
}
for(int y: adj[x])
{
if(y==x && charging[x]==1) ans = true;
if(y==x) continue;
ans |= solve(y);
}
res[x] = ans;
return ans;
};
for(int i = 0;i<n;i++)
{
for(int j = 0;j<used.size();j++) used[j] = 0;
res[i] = -1;
solve(i);
}
return res;
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
n = a.size();
for(int i = 0;i<n;i++)
{
owner[i] = a[i];
charging[i] = r[i];
}
for(int i = 0;i<u.size();i++)
{
adj[ u[i] ].push_back(v[i]);
}
for(int i = 0;i<n;i++)
{
sort(adj[i].begin(), adj[i].end());
auto it = unique(adj[i].begin(), adj[i].end());
adj[i].resize(it-adj[i].begin());
}
int subtask = guessSubtask(a, r, u, v);
if(subtask==1) return solve1();
else if(subtask==3) return solve3();
return {};
}
Compilation message
train.cpp: In function 'int guessSubtask(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int i = 0;i<u.size();i++)
| ~^~~~~~~~~
train.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int i = 0;i<a.size();i++)
| ~^~~~~~~~~
train.cpp: In function 'std::vector<int> solve3()':
train.cpp:205:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
205 | for(int j = 0;j<used.size();j++) used[j] = 0;
| ~^~~~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:223:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
223 | for(int i = 0;i<u.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
896 KB |
Output is correct |
| 2 |
Correct |
6 ms |
896 KB |
Output is correct |
| 3 |
Correct |
5 ms |
896 KB |
Output is correct |
| 4 |
Correct |
6 ms |
896 KB |
Output is correct |
| 5 |
Correct |
6 ms |
896 KB |
Output is correct |
| 6 |
Correct |
5 ms |
896 KB |
Output is correct |
| 7 |
Correct |
5 ms |
896 KB |
Output is correct |
| 8 |
Correct |
5 ms |
896 KB |
Output is correct |
| 9 |
Correct |
5 ms |
896 KB |
Output is correct |
| 10 |
Correct |
4 ms |
896 KB |
Output is correct |
| 11 |
Correct |
5 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
WA in grader: Wrong returned array size |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2049 ms |
20852 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1152 KB |
WA in grader: Wrong returned array size |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1280 KB |
WA in grader: Wrong returned array size |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
896 KB |
Output is correct |
| 2 |
Correct |
6 ms |
896 KB |
Output is correct |
| 3 |
Correct |
5 ms |
896 KB |
Output is correct |
| 4 |
Correct |
6 ms |
896 KB |
Output is correct |
| 5 |
Correct |
6 ms |
896 KB |
Output is correct |
| 6 |
Correct |
5 ms |
896 KB |
Output is correct |
| 7 |
Correct |
5 ms |
896 KB |
Output is correct |
| 8 |
Correct |
5 ms |
896 KB |
Output is correct |
| 9 |
Correct |
5 ms |
896 KB |
Output is correct |
| 10 |
Correct |
4 ms |
896 KB |
Output is correct |
| 11 |
Correct |
5 ms |
896 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
384 KB |
WA in grader: Wrong returned array size |
| 13 |
Halted |
0 ms |
0 KB |
- |
