Submission #1039393

#TimeUsernameProblemLanguageResultExecution timeMemory
1039393Soumya1Toy Train (IOI17_train)C++17
0 / 100
12 ms3420 KiB
#include "train.h" #include <bits/stdc++.h> using namespace std; const int mxN = 5005; set<int> ad[mxN], rev[mxN]; vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) { int n = a.size(); for (int i = 0; i < u.size(); i++) { ad[u[i]].insert(v[i]); rev[v[i]].insert(u[i]); } auto get = [&](vector<int> s, int type) { vector<int> out(n), vis(n); for (int i : s) vis[i] = true; for (int i = 0; i < s.size(); i++) { int u = s[i]; for (int v : rev[u]) { out[v]++; if (!vis[v] && out[v] >= (a[v] ? type : ad[v].size())) { s.push_back(v); vis[v] = true; } } } return s; }; vector<bool> removed(n); while (true) { vector<int> on; for (int i = 0; i < n; i++) { if (r[i] && !removed[i]) on.push_back(i); } vector<bool> can(n); on = get(on, 1); for (int i : on) can[i] = true; vector<int> bad; for (int i = 0; i < n; i++) { if (!removed[i] && !can[i]) bad.push_back(i); } bad = get(bad, 0); if (bad.empty()) break; for (int i : bad) { removed[i] = true; for (int j : ad[i]) rev[j].erase(i); for (int j : rev[i]) ad[j].erase(i); rev[i].clear(); ad[i].clear(); } } vector<int> ans(n); for (int i = 0; i < n; i++) ans[i] = !removed[i]; return ans; }

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:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |  for (int i = 0; i < u.size(); i++) {
      |                  ~~^~~~~~~~~~
train.cpp: In lambda function:
train.cpp:15:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   for (int i = 0; i < s.size(); i++) {
      |                   ~~^~~~~~~~~~
train.cpp:19:27: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'long unsigned int' [-Wsign-compare]
   19 |     if (!vis[v] && out[v] >= (a[v] ? type : ad[v].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...