Submission #406360

#TimeUsernameProblemLanguageResultExecution timeMemory
406360EncryptingWolfToy Train (IOI17_train)C++14
38 / 100
2092 ms2940 KiB
#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 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...