Submission #788661

#	Time	Username	Problem	Language	Result	Execution time	Memory
788661		NeroZein	Toy Train (IOI17_train)	C++17	100 / 100	298 ms	1748 KiB

train

#include "train.h"
#include "bits/stdc++.h"
using namespace std; 

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
  int n = (int) a.size();
  int m = (int) u.size(); 
	vector<int> res(n); 
  vector<vector<int>> g(n), rg(n); 
  for (int i = 0; i < m; ++i) {
    g[u[i]].push_back(v[i]); 
    rg[v[i]].push_back(u[i]); 
  }
  while (true) {
    queue<int> que;
    for (int i = 0; i < n; ++i) {
      if (r[i]) {
        que.push(i); 
      }
    }
    vector<bool> vis(n); 
    vector<int> deg(n);
    for (int i = 0; i < n; ++i) {
      deg[i] = g[i].size();
    }
    while (!que.empty()) {
      int vert = que.front();
      que.pop(); 
      for (int ch : rg[vert]) {
        if (a[ch]) {
          if (!vis[ch]) {
            vis[ch] = true; 
            if (!r[ch]) {
              que.push(ch); 
            }
          }
        } else {
          --deg[ch];
          if (deg[ch] == 0) {
            vis[ch] = true;
            if (!r[ch]) {
              que.push(ch); 
            }
          }
        }
      }
    }
    bool change = false;
    for (int i = 0; i < n; ++i) {
      if (r[i] && !vis[i]) {
        r[i] = 0; 
        change = true;
      }
    }
    if (!change) {
      for (int i = 0; i < n; ++i) {
        res[i] = vis[i]; 
      }
      break; 
    }
  }
	return res;
}

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