oj.uz

Submission #1024559

# Submission time Handle Problem Language Result Execution time Memory
1024559 2024-07-16T07:39:18 Z huutuan Toy Train (IOI17_train) C++14
16 / 100
 734 ms 99628 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 604 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 2 ms 600 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 604 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 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 157 ms 99032 KB Output is correct
2 Correct 192 ms 99200 KB Output is correct
3 Correct 176 ms 99056 KB Output is correct
4 Correct 726 ms 99164 KB Output is correct
5 Correct 555 ms 99180 KB Output is correct
6 Correct 424 ms 99364 KB Output is correct
7 Correct 480 ms 99416 KB Output is correct
8 Correct 308 ms 99400 KB Output is correct
9 Correct 271 ms 99324 KB Output is correct
10 Correct 363 ms 99152 KB Output is correct
11 Correct 299 ms 99156 KB Output is correct
12 Correct 70 ms 83820 KB Output is correct
13 Correct 698 ms 99408 KB Output is correct
14 Correct 678 ms 99416 KB Output is correct
15 Correct 723 ms 99384 KB Output is correct
16 Correct 701 ms 99628 KB Output is correct
17 Correct 733 ms 99424 KB Output is correct
18 Correct 279 ms 98896 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 675 ms 99072 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 734 ms 99056 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 604 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 2 ms 600 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 604 KB Output is correct
12 Incorrect 0 ms 600 KB 3rd lines differ - on the 8th token, expected: '0', found: '1'
13 Halted 0 ms 0 KB -