| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 775979 |
2023-07-07T08:01:05 Z |
peteza |
Toy Train (IOI17_train) |
C++14 |
|
301 ms |
197548 KB |
#include <bits/stdc++.h>
#include "train.h"
using namespace std;
using pii = pair<int, int>;
vector<int> adj[5005], tran[5005];
int dist[5005][5005], disttran[5005][5005];
bool vis[5005], self[5005];
int st;
queue<pii> q;
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
std::vector<int> res(a.size());
for(int i=0;i<u.size();i++)
adj[u[i]].push_back(v[i]),
tran[v[i]].push_back(u[i]),
self[u[i]] |= (u[i] == v[i]);
if(a[0] == 1) { // arezou (sub 3), find cyc with charging station
for(st=0;st<a.size();st++) {
for(int i=0;i<=a.size();i++) { //normal
vis[i] = 0;
dist[st][i] = disttran[st][i] = 1000000000;
}
q.emplace(st, 0);
while(!q.empty()) {
auto e = q.front(); q.pop();
if(vis[e.first]) continue;
vis[e.first] = 1; dist[st][e.first] = e.second;
for(int E:adj[st])
q.emplace(E, e.second+1);
}
for(int i=0;i<=a.size();i++) { //transposed
vis[i] = 0;
}
q.emplace(st, 0);
while(!q.empty()) {
auto e = q.front(); q.pop();
if(vis[e.first]) continue;
vis[e.first] = 1; disttran[st][e.first] = e.second;
for(int E:tran[st])
q.emplace(E, e.second+1);
}
}
for(int i=0;i<a.size();i++) {
if(r[i]) {
bool yas = 0;
for(int k=0;k<a.size();k++) {
if(i != k && (dist[i][k] + disttran[k][i] <= a.size())) {
yas = 1;
break;
}
}
res[i] = yas;
} else {
bool yas = 0;
for(int k=0;k<a.size();k++) {
if(i != k && (dist[i][k] + disttran[k][i] <= a.size()) && r[k]) {
yas = 1;
break;
}
}
res[i] = yas;
}
}
} else { // borzou (sub 4), find cyc with NO charging station
}
return res;
}
Compilation message
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:15:15: 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<u.size();i++)
| ~^~~~~~~~~
train.cpp:20:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(st=0;st<a.size();st++) {
| ~~^~~~~~~~~
train.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int i=0;i<=a.size();i++) { //normal
| ~^~~~~~~~~~
train.cpp:33:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i=0;i<=a.size();i++) { //transposed
| ~^~~~~~~~~~
train.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i=0;i<a.size();i++) {
| ~^~~~~~~~~
train.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int k=0;k<a.size();k++) {
| ~^~~~~~~~~
train.cpp:51:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | if(i != k && (dist[i][k] + disttran[k][i] <= a.size())) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
train.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int k=0;k<a.size();k++) {
| ~^~~~~~~~~
train.cpp:60:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | if(i != k && (dist[i][k] + disttran[k][i] <= a.size()) && r[k]) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1068 KB |
3rd lines differ - on the 14th token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
596 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 |
301 ms |
197548 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 |
6 ms |
1108 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 |
1364 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 |
3 ms |
1068 KB |
3rd lines differ - on the 14th token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
