| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 314422 |
2020-10-19T20:30:39 Z |
hhh07 |
Toy Train (IOI17_train) |
C++14 |
|
9 ms |
1512 KB |
#include <iostream>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#include "train.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
vector<vi> adjList(5005, vi());
vi gotov(5005, false), t;
int n;
vi operator-(vi a, vi b){
sort(a.begin(), a.end());
sort(b.begin(), b.end());
vi res; int j = 0;
for (int i = 0; i < a.size(); i++){
while(j < b.size() && b[j] < a[i])
j++;
if (j == b.size() || b[j] > a[i])
res.push_back(a[i]);
}
return res;
}
int vis[5005], deg[5005];
vi f(bool type, vi x){
for (int i = 0; i < n; i++)
vis[i] = deg[i] = 0;
for (int i = 0; i < n; i++){
if (gotov[i])
continue;
for (int j = 0; j < adjList[i].size(); j++){
int curr = adjList[i][j];
if (!gotov[curr])
deg[curr]++;
}
}
queue<int> q;
for (int i = 0; i < x.size(); i++)
vis[x[i]] = true, q.push(x[i]);
while(!q.empty()){
int curr = q.front();
q.pop();
for (int i = 0; i < adjList[curr].size(); i++){
int k = adjList[curr][i];
if (gotov[k] || vis[k])
continue;
if (t[k] == type)
vis[k] = true, q.push(k);
else{
deg[k]--;
if (!deg[k])
vis[k] = true, q.push(k);
}
}
}
vi res;
for (int i = 0; i < n; i++){
if (!gotov[i] && vis[i])
res.push_back(i);
}
return res;
}
vi who_wins(vi a, vi r, vi u, vi v){
n = a.size(); int m = u.size();
t = a;
for (int i = 0; i < m; i++)
adjList[u[i]].push_back(v[i]);
vi graph;
for (int i = 0; i < n; i++)
graph.push_back(i);
while(!graph.empty()){
vi f_a, f_b;
for (int i = 0; i < graph.size(); i++)
if (r[graph[i]])
f_a.push_back(i);
f_a = f(1, f_a); f_b = f(0, graph - f_a);
if (!f_b.size())
break;
for (int i = 0; i < f_b.size(); i++)
gotov[f_b[i]] = true;
graph = graph - f_b;
}
vi res(n, 0);
for (int i = 0; i < graph.size(); i++)
res[graph[i]] = true;
return res;
}
Compilation message
train.cpp: In function 'vi operator-(vi, vi)':
train.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for (int i = 0; i < a.size(); i++){
| ~~^~~~~~~~~~
train.cpp:23:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | while(j < b.size() && b[j] < a[i])
| ~~^~~~~~~~~~
train.cpp:26:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | if (j == b.size() || b[j] > a[i])
| ~~^~~~~~~~~~~
train.cpp: In function 'vi f(bool, vi)':
train.cpp:42:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int j = 0; j < adjList[i].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~~
train.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i = 0; i < x.size(); i++)
| ~~^~~~~~~~~~
train.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i = 0; i < adjList[curr].size(); i++){
| ~~^~~~~~~~~~~~~~~~~~~~~~
train.cpp: In function 'vi who_wins(vi, vi, vi, vi)':
train.cpp:91:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (int i = 0; i < graph.size(); i++)
| ~~^~~~~~~~~~~~~~
train.cpp:100:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for (int i = 0; i < f_b.size(); i++)
| ~~^~~~~~~~~~~~
train.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for (int i = 0; i < graph.size(); i++)
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
1140 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
1512 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
1280 KB |
3rd lines differ - on the 1st token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
1408 KB |
3rd lines differ - on the 1st token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
1140 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
