Submission #269367

#	Time	Username	Problem	Language	Result	Execution time	Memory
269367		kdh9949	장난감 기차 (IOI17_train)	C++17	100 / 100	467 ms	1784 KiB

train

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define x first
#define y second
#define all(v) v.begin(),v.end()

vint who_wins(vint a, vint r, vint u, vint v) {
  int n = a.size(), m = u.size();
  vector<vint> e(n), re(n);
  for(int i = 0; i < m; i++) {
    e[u[i]].push_back(v[i]);
    re[v[i]].push_back(u[i]);
  }

  vint elim(n), ch(n), vis(n), deg(n), cur(n), ans(n, 1), ev;
  queue<int> q;
  int leftn = n;
  for(int i = 0; i < n; i++) deg[i] = e[i].size();

  while(leftn) {
    fill(all(ch), 0);
    fill(all(vis), 0);
    copy(all(deg), cur.begin());
    for(int i = 0; i < n; i++) if(!elim[i] && r[i]) { ch[i] = vis[i] = 1; q.push(i); }
    while(!q.empty()) {
      int x = q.front();
      q.pop();
      for(int i : re[x]) {
        if(elim[i] || vis[i]) continue;
        cur[i]--;
        if(a[i] || !cur[i]) {
          ch[i] = vis[i] = 1;
          q.push(i);
        }
      }
    }
    if(count(all(ch), 1) == leftn) break;
    
    copy(all(deg), cur.begin());
    ev.resize(0);
    for(int i = 0; i < n; i++) if(!elim[i] && !ch[i]) {
      ev.push_back(i); elim[i] = 1; q.push(i);
    }
    while(!q.empty()) {
      int x = q.front();
      q.pop();
      for(int i : re[x]) {
        if(elim[i]) continue;
        cur[i]--;
        if(!a[i] || !cur[i]) {
          ev.push_back(i);
          elim[i] = 1;
          q.push(i);
        }
      }
    }

    leftn -= int(ev.size());
    for(int x : ev) {
      ans[x] = 0;
      for(int i : re[x]) deg[i]--;
    }
  }

  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