oj.uz

Submission #1024561

# Submission time Handle Problem Language Result Execution time Memory
1024561 2024-07-16T07:45:36 Z huutuan Toy Train (IOI17_train) C++14
27 / 100
 854 ms 99412 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);
      }
   }
}

bool bfs2(int root, int n, vector<int> &r){
   if (r[root]) return 0;
   vector<int> dd(n);
   queue<int> q;
   q.push(root);
   while (q.size()){
      int u=q.front();
      q.pop();
      for (int v:g[u]) if (!dd[v] && !r[v]){
         dd[v]=1;
         q.push(v);
      }
   }
   return dd[root];
}

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, sub3=1, sub4=1;
   for (int i=0; i<m; ++i) sub1&=u[i]==v[i] || u[i]+1==v[i];
   for (int i:a) sub3&=i, sub4&=!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);
   if (sub3){
      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];
      }
      return ans;
   }
   if (sub4){
      vector<int> ans(n, 1);
      for (int i=0; i<n; ++i) if (bfs2(i, n, r)){
         for (int j=0; j<n; ++j) if (d[j][i]) ans[j]=0;
      }
      return ans;
   }
   return vector<int>(n, 0);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 3 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 604 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 3 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 604 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 99060 KB Output is correct
2 Correct 209 ms 98968 KB Output is correct
3 Correct 171 ms 98956 KB Output is correct
4 Correct 772 ms 99152 KB Output is correct
5 Correct 562 ms 99152 KB Output is correct
6 Correct 441 ms 99028 KB Output is correct
7 Correct 487 ms 99156 KB Output is correct
8 Correct 302 ms 99152 KB Output is correct
9 Correct 278 ms 99156 KB Output is correct
10 Correct 363 ms 99152 KB Output is correct
11 Correct 321 ms 98900 KB Output is correct
12 Correct 65 ms 83536 KB Output is correct
13 Correct 722 ms 99156 KB Output is correct
14 Correct 717 ms 99024 KB Output is correct
15 Correct 713 ms 99212 KB Output is correct
16 Correct 721 ms 99024 KB Output is correct
17 Correct 720 ms 99156 KB Output is correct
18 Correct 270 ms 98900 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 99084 KB Output is correct
2 Correct 222 ms 99156 KB Output is correct
3 Correct 395 ms 99412 KB Output is correct
4 Correct 450 ms 99152 KB Output is correct
5 Correct 648 ms 99400 KB Output is correct
6 Correct 544 ms 99412 KB Output is correct
7 Correct 567 ms 99192 KB Output is correct
8 Correct 403 ms 98900 KB Output is correct
9 Correct 55 ms 84520 KB Output is correct
10 Correct 735 ms 99268 KB Output is correct
11 Correct 696 ms 99236 KB Output is correct
12 Correct 722 ms 99412 KB Output is correct
13 Correct 854 ms 99380 KB Output is correct
14 Correct 505 ms 99152 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 744 ms 99152 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
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 3 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 604 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 3 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 604 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -