Submission #163179

#TimeUsernameProblemLanguageResultExecution timeMemory
163179MinnakhmetovToy Train (IOI17_train)C++14
0 / 100
420 ms1528 KiB
#include "train.h" #include <bits/stdc++.h> using namespace std; #define all(aaa) aaa.begin(), aaa.end(); #define ll long long const int N = 5005; vector<int> g[N]; int deg[N], tmp[N]; bool used[N]; int n, m; vector<int> reachable(vector<int> &a, vector<int> v, int master) { for (int i = 0; i < n; i++) { used[i] = 0; tmp[i] = deg[i]; } queue<int> q; auto check = [&](int x) { if (!used[x]) { if (a[x] == master) { used[x] = 1; q.push(x); } else if (--tmp[x] == 0) { used[x] = 1; q.push(x); } } }; for (int x : v) { used[x] = 1; q.push(x); } for (int x : v) { for (int to : g[x]) { check(to); } } while (!q.empty()) { int node = q.front(); q.pop(); for (int to : g[node]) { check(to); } } vector<int> ans; for (int i = 0; i < n; i++) { if (used[i]) ans.push_back(i); } return ans; } vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) { n = a.size(), m = u.size(); for (int i = 0; i < m; i++) { g[v[i]].push_back(u[i]); deg[u[i]]++; } vector<int> res(n, 1); bool work = true; while (work) { work = false; vector<int> sts; for (int i = 0; i < n; i++) { if (r[i]) sts.push_back(i); } vector<int> good = reachable(a, sts, 1), killers; for (int i = 0, j = 0; i < n; i++) { while (j < good.size() && good[j] < i) j++; if (j == good.size() || good[j] != i) killers.push_back(i); } vector<int> bad = reachable(a, killers, 0); for (int x : bad) { if (r[x]) work = true; res[x] = 0; r[x] = 0; } } return res; }

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:89:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (j < good.size() && good[j] < i)
           ~~^~~~~~~~~~~~~
train.cpp:91:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (j == good.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...