| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 46089 |
2018-04-17T08:14:03 Z |
Abelyan |
Toy Train (IOI17_train) |
C++17 |
|
15 ms |
3444 KB |
#include "train.h"
#include <algorithm>
#include <vector>
#include <unordered_set>
#include <queue>
using namespace std;
const int N = 5006;
int n, m;
vector<int> g[N],ing[N];
vector<char> col(n),chrg(n);
void rev(vector<char> &s, vector<char> &ans){
for (int i = 0; i < n; i++){
ans[i] = !s[i];
}
}
void Fw(int w, const vector<char> &s, vector<char> &ans){
static queue<int> q;
ans.resize(0);
for (int i = 0; i < s.size(); i++){
ans.push_back(s[i]);
if (s[i])
q.push(i);
}
while (!q.empty()){
int v = q.front();
q.pop();
for (auto to : ing[v]){
if (ans[to]) continue;
bool mb = true;
for (auto k : g[to]){
mb &= ans[k] == true;
}
if (col[to] == w || mb){
ans[to] = true;
q.push(to);
}
}
}
}
void intersect(const vector<char> &a, const vector<char> &b, vector<char> &ans){
ans.resize(0);
for (int i = 0; i < a.size();i++){
ans.push_back(b[i] && a[i]);
}
}
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[u[i]].push_back(v[i]);
ing[v[i]].push_back(u[i]);
}
for (int i = 0; i < n; i++){
if (a[i]){
col[i] = true;
}
}
for (int i = 0; i < n; i++){
if (r[i]) chrg[i] = true;
}
while (1){
static vector<char> R(n);
for (int i = 0; i < n; i++){
R[i] = chrg[i];
}
static vector<char> far(n), gg(n) , x(n), ht(n);
Fw(1, R, far);
rev(far, gg);
Fw(0, gg, x);
intersect(far, x, ht);
bool mb = false;
for (int i = 0; i < ht.size();i++){
if (ht[i] && chrg[i]) mb = true, chrg[i] = false;
}
if (!mb){
vector<int> ans(n,1);
for (int i = 0; i < x.size();i++){
if (x[i])
ans[i] = 0;
}
return ans;
}
}
}
Compilation message
train.cpp: In function 'void Fw(int, const std::vector<char>&, std::vector<char>&)':
train.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < s.size(); i++){
~~^~~~~~~~~~
train.cpp: In function 'void intersect(const std::vector<char>&, const std::vector<char>&, std::vector<char>&)':
train.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.size();i++){
~~^~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:78:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ht.size();i++){
~~^~~~~~~~~~~
train.cpp:83:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < x.size();i++){
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
1912 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1912 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
2988 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
3056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
3444 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
1912 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
