Submission #561653

#	Time	Username	Problem	Language	Result	Execution time	Memory
561653		iancu	장난감 기차 (IOI17_train)	C++14	100 / 100	437 ms	1620 KiB

train

#include "train.h"
#include <vector>
#include <queue>

using namespace std;

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
  int n = a.size(), m = u.size();
  vector<int> w(n, false);
  vector<bool> curr(n, true);
  vector<vector<int>> prv(n, vector<int>()), nxt(n, vector<int>());
  for (int i = 0; i < m; ++i) {
    prv[v[i]].push_back(u[i]);
    nxt[u[i]].push_back(v[i]);
  }
  while (true) {
    vector<bool> s(n, false);
    queue<int> q;
    for (int i = 0; i < n; ++i)
      if (curr[i] && r[i]) {
        s[i] = true;
        q.push(i);
      }
    while (!q.empty()) {
      auto y = q.front();
      q.pop();
      for (auto x: prv[y])
        if (curr[x] && !s[x]) {
          if (!a[x]) {
            bool isGood = true;
            for (auto z: nxt[x])
              if (curr[z] && !s[z]) {
                isGood = false;
                break;
              }
            if (!isGood)
              continue;
          }
          s[x] = true;
          q.push(x);
        }
    }
    bool allS = true;
    for (int i = 0; i < n; ++i)
      if (s[i] != curr[i]) {
        allS = false;
        break;
      }
    if (allS) {
      for (int i = 0; i < n; ++i)
        w[i] = s[i];
      break;
    }
    vector<bool> nonS(n, false);
    for (int i = 0; i < n; ++i)
      if (curr[i])
        nonS[i] = !s[i];
    for (int i = 0; i < n; ++i)
      if (curr[i] && nonS[i])
        q.push(i);
    while (!q.empty()) {
      auto y = q.front();
      q.pop();
      for (auto x: prv[y])
        if (curr[x] && !nonS[x]) {
          if (a[x]) {
            bool isGood = true;
            for (auto z: nxt[x])
              if (curr[z] && !nonS[z]) {
                isGood = false;
                break;
              }
            if (!isGood)
              continue;
          }
          nonS[x] = true;
          q.push(x);
        }
    }
    for (int i = 0; i < n; ++i)
      if (curr[i] && nonS[i])
        curr[i] = false;
  }
  return w;
}

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