oj.uz

Submission #1024614

# Submission time Handle Problem Language Result Execution time Memory
1024614 2024-07-16T08:37:56 Z huutuan Toy Train (IOI17_train) C++14
27 / 100
 2000 ms 99244 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()){
      for (int j=0; j<(int)ans.size(); ++j){
         vector<int> vis(ans.size());
         int u=j;
         while (!vis[u]){
            vis[u]=1;
            u=nxt[u];
         }
         bool cr=0;
         while (vis[u]==1){
            cr|=rr[u];
            vis[u]=2;
            u=nxt[u];
         }
         if (!cr) 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 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 2 ms 820 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 Correct 1495 ms 544 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 156 ms 348 KB Output is correct
4 Execution timed out 2062 ms 348 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 99156 KB Output is correct
2 Correct 160 ms 99156 KB Output is correct
3 Correct 167 ms 99016 KB Output is correct
4 Correct 766 ms 99104 KB Output is correct
5 Correct 581 ms 99156 KB Output is correct
6 Correct 426 ms 99156 KB Output is correct
7 Correct 472 ms 99152 KB Output is correct
8 Correct 320 ms 99152 KB Output is correct
9 Correct 282 ms 99120 KB Output is correct
10 Correct 376 ms 99152 KB Output is correct
11 Correct 312 ms 98900 KB Output is correct
12 Correct 75 ms 83536 KB Output is correct
13 Correct 756 ms 99156 KB Output is correct
14 Correct 733 ms 99012 KB Output is correct
15 Correct 766 ms 99136 KB Output is correct
16 Correct 751 ms 99152 KB Output is correct
17 Correct 740 ms 99244 KB Output is correct
18 Correct 283 ms 98896 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 99136 KB Output is correct
2 Correct 221 ms 99156 KB Output is correct
3 Correct 404 ms 99152 KB Output is correct
4 Correct 452 ms 99156 KB Output is correct
5 Correct 631 ms 99156 KB Output is correct
6 Correct 532 ms 99100 KB Output is correct
7 Correct 574 ms 99208 KB Output is correct
8 Correct 417 ms 98900 KB Output is correct
9 Correct 56 ms 84156 KB Output is correct
10 Correct 774 ms 99152 KB Output is correct
11 Correct 732 ms 99224 KB Output is correct
12 Correct 753 ms 99156 KB Output is correct
13 Correct 828 ms 99152 KB Output is correct
14 Correct 494 ms 99156 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 712 ms 99108 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 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 2 ms 820 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 Correct 1495 ms 544 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 156 ms 348 KB Output is correct
15 Execution timed out 2062 ms 348 KB Time limit exceeded
16 Halted 0 ms 0 KB -