Submission #134142

#	Time	Username	Problem	Language	Result	Execution time	Memory
134142		IOrtroiii	Toy Train (IOI17_train)	C++14	100 / 100	688 ms	1528 KiB

train

#include <bits/stdc++.h>

#include "train.h"

using namespace std;

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
   int n = a.size();
   int m = u.size();
   vector<int> deg(n);
   vector<vector<int>> g(n);
   for (int i = 0; i < m; ++i) {
      ++deg[u[i]];
      g[v[i]].push_back(u[i]);
   }
   while (true) {
      vector<int> ans = r;
      {
         queue<int> q;
         vector<int> cdeg = deg;
         for (int i = 0; i < n; ++i) {
            if (ans[i]) {
               q.push(i);
            }
         }
         while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g[u]) {
               if (!ans[v]) {
                  if (a[v] || (--cdeg[v]) == 0) {
                     ans[v] = 1;
                     q.push(v);
                  }
               }
            }
         }
      }
      {
         queue<int> q;
         vector<int> cdeg = deg;
         for (int i = 0; i < n; ++i) {
            if (!ans[i]) {
               q.push(i);
            }
         }
         while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g[u]) {
               if (ans[v]) {
                  if (!a[v] || (--cdeg[v]) == 0) {
                     ans[v] = 0;
                     q.push(v);
                  }
               }
            }
         }
      }
      bool finish = true;
      for (int i = 0; i < n; ++i) {
         if (!ans[i] && r[i]) {
            r[i] = 0;
            finish = false;
         }
      }
      if (finish) {
         return ans;
      }
   }
}

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