oj.uz

Submission #1024609

# Submission time Handle Problem Language Result Execution time Memory
1024609 2024-07-16T08:36:02 Z huutuan Toy Train (IOI17_train) C++14
27 / 100
 841 ms 99592 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> va, vb;
int nxt[N];
vector<int> ans, cur, rr;

void backtrackb(int i){
   if (i==(int)vb.size()){
      vector<int> vis(ans.size());
      for (int j=0; j<(int)ans.size(); ++j){
         int u=j;
         while (!vis[u]){
            vis[u]=1;
            u=nxt[u];
         }
         if (vis[u]==1){
            bool cr=0;
            while (vis[u]==1){
               cr|=rr[u];
               vis[u]=2;
               u=nxt[u];
            }
            if (cr){
               while (vis[u]==2){
                  vis[u]=3;
                  u=nxt[u];
               }
            }else{
               while (vis[u]==2){
                  vis[u]=4;
                  u=nxt[u];
               }
            }
         }
         if (vis[u]==4) cur[j]=0;
      }
      return;
   }
   int u=vb[i];
   for (int v:g[u]){
      nxt[u]=v;
      backtrackb(i+1);
   }
}

void backtracka(int i){
   if (i==(int)va.size()){
      cur=vector<int>(ans.size(), 1);
      backtrackb(0);
      for (int j=0; j<(int)ans.size(); ++j) ans[j]|=cur[j];
      return;
   }
   int u=va[i];
   for (int v:g[u]){
      nxt[u]=v;
      backtracka(i+1);
   }
}

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, sub2=1, sub3=1, sub4=1;
   for (int i=0; i<m; ++i) sub1&=u[i]==v[i] || u[i]+1==v[i];
   sub2&=n<=15;
   for (int i:a) sub3&=i, sub4&=!i;
   ans.resize(n, 0);
   rr=r;
   if (sub1){
      vector<int> 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]);
   if (sub2){
      for (int i=0; i<n; ++i){
         if (a[i]) va.push_back(i);
         else vb.push_back(i);
      }
      backtracka(0);
      return ans;
   }
   for (int i=0; i<n; ++i) bfs(i);
   if (sub3){
      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){
      fill(ans.begin(), ans.end(), 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 856 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 856 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 2 ms 860 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 424 ms 348 KB 3rd lines differ - on the 7th 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 159 ms 99156 KB Output is correct
2 Correct 162 ms 99156 KB Output is correct
3 Correct 173 ms 99264 KB Output is correct
4 Correct 769 ms 99420 KB Output is correct
5 Correct 579 ms 99352 KB Output is correct
6 Correct 430 ms 99352 KB Output is correct
7 Correct 472 ms 99324 KB Output is correct
8 Correct 304 ms 99424 KB Output is correct
9 Correct 269 ms 99384 KB Output is correct
10 Correct 361 ms 99156 KB Output is correct
11 Correct 317 ms 99236 KB Output is correct
12 Correct 74 ms 83792 KB Output is correct
13 Correct 787 ms 99464 KB Output is correct
14 Correct 720 ms 99412 KB Output is correct
15 Correct 747 ms 99372 KB Output is correct
16 Correct 715 ms 99216 KB Output is correct
17 Correct 703 ms 99412 KB Output is correct
18 Correct 279 ms 98980 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 99284 KB Output is correct
2 Correct 219 ms 99152 KB Output is correct
3 Correct 398 ms 99424 KB Output is correct
4 Correct 492 ms 99360 KB Output is correct
5 Correct 624 ms 99328 KB Output is correct
6 Correct 517 ms 99412 KB Output is correct
7 Correct 585 ms 99360 KB Output is correct
8 Correct 391 ms 99152 KB Output is correct
9 Correct 57 ms 84304 KB Output is correct
10 Correct 706 ms 99408 KB Output is correct
11 Correct 717 ms 99448 KB Output is correct
12 Correct 767 ms 99228 KB Output is correct
13 Correct 841 ms 99592 KB Output is correct
14 Correct 506 ms 99412 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 714 ms 99412 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 856 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 856 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Incorrect 424 ms 348 KB 3rd lines differ - on the 7th token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -