oj.uz

Submission #68179

# Submission time Handle Problem Language Result Execution time Memory
68179 2018-08-16T07:41:58 Z mirbek01 Toy Train (IOI17_train) C++17
27 / 100
 1238 ms 4172 KB 
#include "train.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 2;

int n, m, used[N], vr;
vector <int> g[N], G[N], r, res;
bool fl;

void dfs(int v){
      used[v] = 1;
      for(int to : g[v]){
            if(used[to] == 1){
                  if(to == vr) fl = 1;
            } else if(!used[to])
                  dfs(to);
      }
      used[v] = 2;
}

void dfs1(int v){
      used[v] = 1;
      for(int to : g[v]){
            if(r[to]) continue;
            if(used[to] == 1){
                  fl = 1;
            } else if(!used[to])
                  dfs1(to);
      }
      used[v] = 2;
}

void bfs(int s){
      memset(used, 0, sizeof(used));
      queue <int> q;
      q.push(s);
      used[s] = 1;
      while(!q.empty()){
            int v = q.front();
            res[v] = 1;
            q.pop();
            for(int to : G[v]){
                  if(used[to]) continue;
                  used[to] = 1;
                  q.push(to);
            }
      }
}

vector<int> who_wins(vector<int> a, vector<int> R, vector<int> u, vector<int> v) {
	n = (int)(a.size());
	m = (int)(u.size());
	r = R;
      res.resize(n);
      int sum = 0;
      for(int i = 0; i < n; i ++){
            sum += a[i];
      }

      map < pair <int, int>, int > mp;

      for(int i = 0; i < m; i ++){
            mp[{u[i], v[i]}] = 1;
            g[u[i]].push_back(v[i]);
            G[v[i]].push_back(u[i]);
      }

      if(sum == n){
            for(int s = 0; s < n; s ++){
                  if(r[s]){
                        memset(used, 0, sizeof(used));
                        fl = 0;
                        vr = s;
                        dfs(s);
                        if(fl){
                              bfs(s);
                        }
                  }
            }
      } else if(!sum){
            for(int s = 0; s < n; s ++){
                  if(!r[s]){
                        memset(used, 0, sizeof(used));
                        fl = 0;
                        dfs1(s);
                        if(fl){
                              bfs(s);
                        }
                  }
            }
            for(int s = 0; s < n; s ++)
                  res[s] = 1 - res[s];
      } else {
            for(int s = n - 1; s >= 0; s --){
                  if(s == n - 1){
                        if(r[s])
                              res[s] = 1;
                        else
                              res[s] = 0;
                  } else {
                        if(r[s]){
                              if(a[s]){
                                    if(mp[{s, s}])
                                          res[s] = 1;
                                    else
                                          res[s] = res[s + 1];
                              }
                              else{
                                    if(mp[{s, s + 1}])
                                          res[s] = res[s + 1];
                                    else
                                          res[s] = 1;
                              }
                        } else {
                              if(a[s]){
                                    if(mp[{s, s + 1}])
                                          res[s] = res[s + 1];
                                    else
                                          res[s] = 0;
                              }
                              else{
                                    if(mp[{s, s}])
                                          res[s] = 0;
                                    else
                                          res[s] = res[s + 1];
                              }
                        }
                  }
            }
      }

	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1656 KB Output is correct
2 Correct 19 ms 1844 KB Output is correct
3 Correct 14 ms 1940 KB Output is correct
4 Correct 17 ms 2116 KB Output is correct
5 Correct 13 ms 2260 KB Output is correct
6 Correct 14 ms 2272 KB Output is correct
7 Correct 13 ms 2456 KB Output is correct
8 Correct 14 ms 2564 KB Output is correct
9 Correct 14 ms 2648 KB Output is correct
10 Correct 14 ms 2728 KB Output is correct
11 Correct 12 ms 2808 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2808 KB 3rd lines differ - on the 1st 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 32 ms 4028 KB Output is correct
2 Correct 75 ms 4056 KB Output is correct
3 Correct 139 ms 4156 KB Output is correct
4 Correct 861 ms 4156 KB Output is correct
5 Correct 124 ms 4156 KB Output is correct
6 Correct 142 ms 4156 KB Output is correct
7 Correct 840 ms 4156 KB Output is correct
8 Correct 23 ms 4156 KB Output is correct
9 Correct 19 ms 4156 KB Output is correct
10 Correct 29 ms 4156 KB Output is correct
11 Correct 22 ms 4156 KB Output is correct
12 Correct 19 ms 4156 KB Output is correct
13 Correct 26 ms 4156 KB Output is correct
14 Correct 22 ms 4156 KB Output is correct
15 Correct 26 ms 4156 KB Output is correct
16 Correct 25 ms 4156 KB Output is correct
17 Correct 23 ms 4156 KB Output is correct
18 Correct 290 ms 4156 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4156 KB Output is correct
2 Correct 177 ms 4156 KB Output is correct
3 Correct 584 ms 4156 KB Output is correct
4 Correct 276 ms 4156 KB Output is correct
5 Correct 718 ms 4156 KB Output is correct
6 Correct 494 ms 4156 KB Output is correct
7 Correct 480 ms 4156 KB Output is correct
8 Correct 476 ms 4156 KB Output is correct
9 Correct 21 ms 4156 KB Output is correct
10 Correct 25 ms 4156 KB Output is correct
11 Correct 25 ms 4156 KB Output is correct
12 Correct 26 ms 4156 KB Output is correct
13 Correct 1238 ms 4156 KB Output is correct
14 Correct 587 ms 4156 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 4172 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 16 ms 1656 KB Output is correct
2 Correct 19 ms 1844 KB Output is correct
3 Correct 14 ms 1940 KB Output is correct
4 Correct 17 ms 2116 KB Output is correct
5 Correct 13 ms 2260 KB Output is correct
6 Correct 14 ms 2272 KB Output is correct
7 Correct 13 ms 2456 KB Output is correct
8 Correct 14 ms 2564 KB Output is correct
9 Correct 14 ms 2648 KB Output is correct
10 Correct 14 ms 2728 KB Output is correct
11 Correct 12 ms 2808 KB Output is correct
12 Incorrect 3 ms 2808 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
13 Halted 0 ms 0 KB -