oj.uz

Submission #1024560

# Submission time Handle Problem Language Result Execution time Memory
1024560 2024-07-16T07:39:29 Z huutuan Toy Train (IOI17_train) C++14
16 / 100
 726 ms 99216 KB 
#include "train.h"

#include <bits/stdc++.h>

using namespace std;

const int N=5010;
vector<int> g[N];
int d[N][N];

void bfs(int root){
   queue<int> q;
   q.push(root);
   while (q.size()){
      int u=q.front();
      q.pop();
      for (int v:g[u]) if (!d[root][v]){
         d[root][v]=1;
         q.push(v);
      }
   }
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
   int n=a.size(), m=u.size();
   bool sub1=1;
   for (int i=0; i<m; ++i) sub1&=u[i]==v[i] || u[i]+1==v[i];
   if (sub1){
      vector<int> ans(n), cyc(n);
      for (int i=0; i<m; ++i) if (u[i]==v[i]) cyc[u[i]]|=1; else cyc[u[i]]|=2;
      for (int i=n-1; i>=0; --i){
         if (cyc[i]==1){
            ans[i]=r[i];
         }else if (cyc[i]==2){
            ans[i]=ans[i+1];
         }else{
            if (a[i]) ans[i]=r[i] || ans[i+1];
            else ans[i]=r[i] && ans[i+1];
         }
      }
      return ans;
   }
   for (int i=0; i<m; ++i) g[u[i]].push_back(v[i]);
   for (int i=0; i<n; ++i) bfs(i);
   vector<int> ans(n);
   for (int i=0; i<n; ++i){
      for (int j=0; j<n; ++j) if (r[j]) ans[i]|=d[i][j] && d[j][j];
   }
   for (int i=0; i<n; ++i) g[i].clear();
   for (int i=0; i<n; ++i) for (int j=0; j<n; ++j) d[i][j]=0;
   return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 600 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 604 KB 3rd lines differ - on the 8th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 99108 KB Output is correct
2 Correct 166 ms 98988 KB Output is correct
3 Correct 171 ms 99052 KB Output is correct
4 Correct 699 ms 99200 KB Output is correct
5 Correct 597 ms 99152 KB Output is correct
6 Correct 450 ms 99044 KB Output is correct
7 Correct 505 ms 99040 KB Output is correct
8 Correct 308 ms 98964 KB Output is correct
9 Correct 293 ms 99076 KB Output is correct
10 Correct 390 ms 99156 KB Output is correct
11 Correct 329 ms 98952 KB Output is correct
12 Correct 85 ms 98900 KB Output is correct
13 Correct 721 ms 99084 KB Output is correct
14 Correct 712 ms 99068 KB Output is correct
15 Correct 722 ms 99152 KB Output is correct
16 Correct 724 ms 99216 KB Output is correct
17 Correct 716 ms 99080 KB Output is correct
18 Correct 262 ms 98900 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 662 ms 98896 KB 3rd lines differ - on the 696th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 726 ms 99156 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Incorrect 0 ms 604 KB 3rd lines differ - on the 8th token, expected: '0', found: '1'
13 Halted 0 ms 0 KB -