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 <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <tuple>
typedef long long ll;
#define FOR(i,x,y) for(ll i = x; i < y; i++)
using namespace std;
vector<int> players;
vector<set<ll>> adj;
vector<ll> inCounts;
set<ll> badNodesF;
set<ll> batteries;
set<ll> nodesLeft;
void dfs(ll node, bool playerWants, set<ll>& badNodes, vector<ll>& visited, bool losing)
{
if (badNodesF.count(node))
return;
visited[node]++;
if (players[node] == playerWants)
{
if (visited[node] != 1)
return;
else
{
badNodes.emplace(node);
}
}
else
{
if (losing&&visited[node] <= inCounts[node])
{
visited[node] = inCounts[node] + 2; badNodes.emplace(node);
}
else {
if (visited[node] != inCounts[node])
{
return;
}
else
{
badNodes.emplace(node);
}
}
}
for (auto i : adj[node])
{
dfs(i, playerWants, badNodes, visited, false);
}
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
ll n = a.size();
players = a;
inCounts.resize(n);
adj.resize(n);
FOR(i, 0, u.size())
{
adj[v[i]].emplace(u[i]);
inCounts[u[i]] += 1;
}
FOR(i, 0, n)
{
if (r[i])
batteries.emplace(i);
nodesLeft.emplace(i);
}
while (true)
{
vector<ll> visited(n);
set<ll> badNodes;
for (auto i : batteries)
{
badNodes.emplace(i);
dfs(i, true, badNodes, visited, true);
}
set<ll> badNodes2;
vector<ll> visited2(n);
for (auto i : nodesLeft)
{
if (badNodes.count(i) == 0 && badNodesF.count(i)==0)
{
badNodes2.emplace(i);
dfs(i, false, badNodes2, visited2, true);
}
}
for (auto i : badNodes2)
{
// if (badNodes2.count(i))
// {
r[i] = 0;
batteries.erase(i);
// }
}
if (badNodes2.size()==0)
break;
/*for (auto i : badNodes2)
cout << i;*/
//cout << endl;
//badNodesF = badNodes2;
for (auto j : nodesLeft)
{
auto& i = adj[j];
for (auto j : badNodes2)
{
i.erase(j);
}
}
for (auto i : badNodes2)
{
nodesLeft.erase(i);
badNodesF.emplace(i);
for (auto j : adj[i])
inCounts[j]--;
}
}
// !badNodes is B
// Badnodes2 are B
// Neither is B
vector<int> re;
FOR(i, 0, n)
{
if (badNodesF.count(i))
re.push_back(0);
else
re.push_back(1);
}
return re;
}
Compilation message (stderr)
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:8:36: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | #define FOR(i,x,y) for(ll i = x; i < y; i++)
......
65 | FOR(i, 0, u.size())
| ~~~~~~~~~~~~~~
train.cpp:65:2: note: in expansion of macro 'FOR'
65 | FOR(i, 0, u.size())
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |