Submission #296882

#	Time	Username	Problem	Language	Result	Execution time	Memory
296882		ASDF123	Toy Train (IOI17_train)	C++17	5 / 100	12 ms	3712 KiB

train

#include "train.h"
//#include "grader.cpp"
#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];
  
  bool need() {
    bool ans = 1;
    for (int i = 0; i < szof(u); i++) {
      ans &= (u[i] == v[i] || u[i] + 1 == v[i]);
    }
    return ans;
  }
  
  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);
  if (subtask1.need()) {
    subtask1.solve(res);
  } else {
    assert(false);
  }
  return res;
}
 

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51