# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
405701 |
2021-05-16T19:29:00 Z |
rqi |
Toy Train (IOI17_train) |
C++14 |
|
1164 ms |
1528 KB |
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
const int MOD = 1e9+7;
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define pb push_back
void ckmin(pi& a, pi b){
a = min(a, b);
}
void ckmax(pi& a, pi b){
a = max(a, b);
}
const int mx = 5005;
int n, m;
vi a, r, u, v;
vi adj[mx];
array<pi, mx> dp;
array<pi, mx> ndp;
int trans_ans[mx];
vi cur_ans;
void genCurAns(int node){
assert(trans_ans[node] != -1);
assert(cur_ans[node] > 1);
// cout << "node: " << node << "\n";
// for(int i = 0; i < n; i++){
// cout << "cur_ans[" << i << "]: " << cur_ans[i] << "\n";
// }
if(cur_ans[trans_ans[node]] <= 1){
cur_ans[node] = cur_ans[trans_ans[node]];
return;
}
cur_ans[node] = 3;
if(cur_ans[trans_ans[node]] == 2){
genCurAns(trans_ans[node]);
cur_ans[node] = cur_ans[trans_ans[node]];
return;
}
else{
assert(cur_ans[trans_ans[node]] == 3);
int sum = r[node];
int cur_node = trans_ans[node];
while(cur_node != node){
sum+=r[cur_node];
cur_node = trans_ans[cur_node];
}
if(sum >= 1){
cur_ans[node] = 1;
}
else{
cur_ans[node] = 0;
}
return;
}
}
vi getAnsFromTrans(){
cur_ans = vi(n, 2);
for(int i = 0; i < n; i++){
if(cur_ans[i] == 2){
genCurAns(i);
}
}
return cur_ans;
}
vi who_wins(vi _a, vi _r, vi _u, vi _v) {
a = _a;
r = _r;
u = _u;
v = _v;
n = sz(a);
m = sz(u);
for(int i = 0; i < m; i++){
adj[u[i]].pb(v[i]);
}
for(int i = 0; i < n; i++){
dp[i] = mp(0, -1);
}
for(int rep = 0; rep < 5005; rep++){
for(int i = 0; i < n; i++){
if(a[i]){
ndp[i] = mp(-MOD, -1);
}
else{
ndp[i] = mp(MOD, -1);
}
}
for(int i = 0; i < n; i++){
if(a[i]){
for(int& u: adj[i]){
ckmax(ndp[i], mp(dp[u].f, u));
}
}
else{
for(int& u: adj[i]){
ckmin(ndp[i], mp(dp[u].f, u));
}
}
if(r[i]){
ndp[i].f++;
}
}
swap(dp, ndp);
}
vi ans(n, 0);
for(int i = 0; i < n; i++){
if(dp[i].f > 1000){
ans[i] = 1;
}
}
return ans;
for(int i = 0; i < n; i++){
cout << i << " " << dp[i].f << " " << dp[i].s << "\n";
}
for(int i = 0; i < n; i++){
trans_ans[i] = dp[i].s;
cout << "i, trans[i]: " << i << " " << trans_ans[i] << "\n";
assert(trans_ans[i] != -1);
}
return getAnsFromTrans();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
468 ms |
972 KB |
Output is correct |
2 |
Correct |
544 ms |
984 KB |
Output is correct |
3 |
Correct |
515 ms |
984 KB |
Output is correct |
4 |
Correct |
503 ms |
1000 KB |
Output is correct |
5 |
Correct |
489 ms |
984 KB |
Output is correct |
6 |
Correct |
480 ms |
980 KB |
Output is correct |
7 |
Correct |
392 ms |
988 KB |
Output is correct |
8 |
Correct |
337 ms |
1016 KB |
Output is correct |
9 |
Correct |
507 ms |
1092 KB |
Output is correct |
10 |
Correct |
432 ms |
1092 KB |
Output is correct |
11 |
Correct |
362 ms |
940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
460 KB |
Output is correct |
2 |
Correct |
73 ms |
476 KB |
Output is correct |
3 |
Correct |
59 ms |
492 KB |
Output is correct |
4 |
Correct |
57 ms |
460 KB |
Output is correct |
5 |
Correct |
56 ms |
420 KB |
Output is correct |
6 |
Correct |
58 ms |
460 KB |
Output is correct |
7 |
Correct |
56 ms |
476 KB |
Output is correct |
8 |
Correct |
67 ms |
420 KB |
Output is correct |
9 |
Correct |
58 ms |
476 KB |
Output is correct |
10 |
Correct |
57 ms |
460 KB |
Output is correct |
11 |
Correct |
58 ms |
476 KB |
Output is correct |
12 |
Correct |
59 ms |
476 KB |
Output is correct |
13 |
Correct |
57 ms |
460 KB |
Output is correct |
14 |
Correct |
60 ms |
460 KB |
Output is correct |
15 |
Correct |
57 ms |
476 KB |
Output is correct |
16 |
Correct |
57 ms |
476 KB |
Output is correct |
17 |
Correct |
57 ms |
492 KB |
Output is correct |
18 |
Correct |
56 ms |
460 KB |
Output is correct |
19 |
Correct |
57 ms |
460 KB |
Output is correct |
20 |
Correct |
57 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
653 ms |
1508 KB |
Output is correct |
2 |
Correct |
699 ms |
1528 KB |
Output is correct |
3 |
Incorrect |
636 ms |
1496 KB |
3rd lines differ - on the 2nd token, expected: '0', found: '1' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
926 ms |
1272 KB |
Output is correct |
2 |
Incorrect |
809 ms |
1476 KB |
3rd lines differ - on the 1st token, expected: '1', found: '0' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1164 ms |
1484 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 |
Correct |
468 ms |
972 KB |
Output is correct |
2 |
Correct |
544 ms |
984 KB |
Output is correct |
3 |
Correct |
515 ms |
984 KB |
Output is correct |
4 |
Correct |
503 ms |
1000 KB |
Output is correct |
5 |
Correct |
489 ms |
984 KB |
Output is correct |
6 |
Correct |
480 ms |
980 KB |
Output is correct |
7 |
Correct |
392 ms |
988 KB |
Output is correct |
8 |
Correct |
337 ms |
1016 KB |
Output is correct |
9 |
Correct |
507 ms |
1092 KB |
Output is correct |
10 |
Correct |
432 ms |
1092 KB |
Output is correct |
11 |
Correct |
362 ms |
940 KB |
Output is correct |
12 |
Correct |
62 ms |
460 KB |
Output is correct |
13 |
Correct |
73 ms |
476 KB |
Output is correct |
14 |
Correct |
59 ms |
492 KB |
Output is correct |
15 |
Correct |
57 ms |
460 KB |
Output is correct |
16 |
Correct |
56 ms |
420 KB |
Output is correct |
17 |
Correct |
58 ms |
460 KB |
Output is correct |
18 |
Correct |
56 ms |
476 KB |
Output is correct |
19 |
Correct |
67 ms |
420 KB |
Output is correct |
20 |
Correct |
58 ms |
476 KB |
Output is correct |
21 |
Correct |
57 ms |
460 KB |
Output is correct |
22 |
Correct |
58 ms |
476 KB |
Output is correct |
23 |
Correct |
59 ms |
476 KB |
Output is correct |
24 |
Correct |
57 ms |
460 KB |
Output is correct |
25 |
Correct |
60 ms |
460 KB |
Output is correct |
26 |
Correct |
57 ms |
476 KB |
Output is correct |
27 |
Correct |
57 ms |
476 KB |
Output is correct |
28 |
Correct |
57 ms |
492 KB |
Output is correct |
29 |
Correct |
56 ms |
460 KB |
Output is correct |
30 |
Correct |
57 ms |
460 KB |
Output is correct |
31 |
Correct |
57 ms |
460 KB |
Output is correct |
32 |
Correct |
653 ms |
1508 KB |
Output is correct |
33 |
Correct |
699 ms |
1528 KB |
Output is correct |
34 |
Incorrect |
636 ms |
1496 KB |
3rd lines differ - on the 2nd token, expected: '0', found: '1' |
35 |
Halted |
0 ms |
0 KB |
- |