oj.uz

Submission #294214

# Submission time Handle Problem Language Result Execution time Memory
294214 2020-09-08T17:13:22 Z ASDF123 Toy Train (IOI17_train) C++14
5 / 100
 2000 ms 2048 KB 
//#include "train.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()

using namespace std;

typedef vector<int> vi;

const int MAXN = 5001;

struct LineSolve {
  vi a, r, u, v;
  int n, m;
  
  vector <int> g[MAXN];
  vector <int> rg[MAXN];
  
  LineSolve (vi A, vi R, vi U, vi V) {
    a = A;
    r = R;
    u = U;
    v = V;
    n = szof(a);
    m = szof(u);
    for (int i = 0; i < m; i++) {
      g[u[i]].push_back(v[i]);
      rg[v[i]].push_back(u[i]);
    }
  }
  int calc(int pos) {
    int v = pos, can = n;
    while (1) {
      if (r[v]) {
        can = n;
      }
      if (!can) {
        return 0;
      }
      if (szof(g[v]) == 1) {
        if (g[v][0] == v) {
          if (r[v]) {
            return 1;
          } else {
            return 0;
          }
        } else {
          v = g[v][0];
          can--;
          continue;
        }
      }
      else { // 2 types of edges
        if (a[v]) { // Arezou
          if (r[v]) {
            return 1;
          }
          else {
            v = (g[v][0] == v ? g[v][1] : g[v][0]);
            can--;
            continue;
          }
        } else { // Borzou
          if (r[v] == 0) {
            return 0;
          }
          else {
            v = (g[v][0] == v ? g[v][1] : g[v][0]);
            can--;
            continue;
          }
        } 
      }
    }
  }
  void solve(vector <int> &ans) {
    for (int i = 0; i < n; i++) {
      ans[i] = calc(i);
    }
  }
};

vi who_wins(vi a, vi r, vi u, vi v) {
	vi res(a.size(), -1);
  LineSolve subtask1(a, r, u, v);
  subtask1.solve(res);
  return res;
}


//signed main() {
  //int n, m;
  //cin >> n >> m;
  //vector <int> a(n), r(n);
  //vector <int> u(m), v(m);
  //for (int i = 0; i < n; i++) {
    //cin >> a[i];
  //}
  //for (int i = 0; i < n; i++) {
    //cin >> r[i];
  //}
  //for (int i = 0; i < m; i++) {
    //cin >> u[i];
  //}
  //for (int i = 0; i < m; i++) {
    //cin >> v[i];
  //}
  //vector <int> ans = who_wins(a, r, u, v);
  //for (int i = 0; i < n; i++) {
    //cout << i << ": " << ans[i] << endl;
  //}
//}
/*
7 7
0 1 0 1 0 1 0
1 0 0 0 1 0 1
0 1 2 3 4 5 6
0 2 3 4 4 6 6
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1280 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 6 ms 1280 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 5 ms 1280 KB Output is correct
8 Correct 5 ms 1280 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 4 ms 1280 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 1792 KB Output is correct
2 Correct 96 ms 2048 KB Output is correct
3 Correct 86 ms 2048 KB Output is correct
4 Incorrect 10 ms 1920 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2097 ms 1536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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