Submission #1128906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128906		raincity	Toy Train (IOI17_train)	C++17	0 / 100	6 ms	1604 KiB

train

#include "train.h"

#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)
#define len(x) int((x).size())

using i64 = long long;

constexpr int N = 5005;

int n, m;
bool a[N], r[N];
vector<int> adj[N], adjR[N];

int ti, dfn[N], low[N], col[N];
int top, st[N];
int tot;

void tarjan(int u) {
  dfn[u] = low[u] = ++ti, st[++top] = u;
  for (int v : adj[u]) {
    if (a[v] == 1 || r[v] == 1) {
      continue;
    }
    if (dfn[v] == 0) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (col[v] == 0) {
      low[u] = min(low[u], dfn[v]);
    }
  }
  if (dfn[u] == low[u]) {
    ++tot;
    int x;
    do {
      x = st[top--], col[x] = tot;
    } while (x != u);
  }
}

bool hasV[N], hasE[N], ok[N];

void dfsMark(int u) {
  if (ok[u]) {
    return;
  }
  ok[u] = true;
  for (int v : adjR[u]) {
    if (a[v] == 0) {
      dfsMark(v);
    }
  }
}

bool fl;

vector<int> who_wins(vector<int> a_, vector<int> r_, vector<int> u,
                     vector<int> v) {
  assert(!fl);
  fl = true;
  n = len(a_);
  memcpy(a + 1, a_.data(), n * sizeof a[0]);
  memcpy(r + 1, r_.data(), n * sizeof a[0]);
  m = len(u);
  for (int i = 0; i < m; ++i) {
    ++u[i], ++v[i];
    adj[u[i]].push_back(v[i]);
    adjR[v[i]].push_back(u[i]);
  }
  for (int i = 1; i <= n; ++i) {
    if (dfn[i] == 0 && a[i] == 0 && r[i] == 0) {
      tarjan(i);
    }
  }
  for (int i = 0; i < m; ++i) {
    const int x = col[u[i]], y = col[v[i]];
    if (x == y) {
      hasE[x] = true;
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (r[i] == 1) {
      hasV[col[i]] = true;
    }
  }
  bool any = false;
  for (int i = 1; i <= n; ++i) {
    if (a[i] == 1 && r[i] == 1) {
      any = true;
      break;
    }
  }
  if (any) {
    for (int i = 1; i <= n; ++i) {
      if (a[i] == 0 && !hasV[col[i]] && hasE[col[i]]) {
        dfsMark(i);
      }
    }
    vector<int> ans(n);
    for (int i = 1; i <= n; ++i) {
      if (ok[i]) {
        ans[i - 1] = 1;
      }
    }
    return ans;
  } else {
    bool fl = false;
    for (int i = 1; i <= tot; ++i) {
      if (!hasV[i] && hasE[i]) {
        fl = true;
        break;
      }
    }
    return vector<int>(n, fl);
  }
}

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