답안 #577091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
577091	2022-06-14T04:22:05 Z	Kanon	장난감 기차 (IOI17_train)	C++14	11 / 100	1210 ms	99740 KB

train

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> who_wins(vector<int> owned, vector<int> z, vector<int> From, vector<int> To) {
  int n = owned.size();
  int m = To.size();
  vector<vector<int>> g(n);
  vector<vector<int>> Rev(n);
  for (int i = 0; i < m; i++) {
    g[From[i]].push_back(To[i]);
    Rev[To[i]].push_back(From[i]);
  }
 
  vector<int> ret(n, -1);
 
  {
    vector<int> was(n);
    vector<int> alive(n);
    function<void(int)> dfs = [&] (int v) {
      was[v] = 1;
      for (int i : g[v]) {
        if (alive[i] && !was[i]) {
          dfs(i);
        }
      }
    };
 
    auto winstate = [&](vector<int> keep, vector<int> nodes) {
      fill(alive.begin(), alive.end(), 0);
      for (int i : keep) {
        alive[i] = 1;
      }
 
      vector<vector<int>> r(n);
      for (int i = 0; i < n; i++) {
        if (!alive[i]) {
          continue;
        }
        dfs(i);
        r[i] = was;
        fill(was.begin(), was.end(), 0);
      }
 
      vector<bool> win(n);
      for (int i : nodes) {
        for (int j : g[i]) {
          if (alive[j] && r[j][i] == 1) {
            win[i] = true;
          }
        }
      }
      return win;
    };
 
    auto get_win = [&](vector<int> keep, vector<bool> &win) {
      while (true) {
        bool change = false;
        for (int i : keep) {
          if (win[i]) {
            continue;
          }
          for (int j : g[i]) {
            if (win[j]) {
              win[i] = true;
              change = true;
            }
          }
        }
        if (!change) {
          break;
        }
      }
    };
 
    for (int player = 1; player < 2; player++) {
      vector<int> keep;
      vector<int> nodes;
 
      for (int i = 0; i < n; i++) {
        if (owned[i] != player) {
          continue;
        }
        if (player == 1) {
          keep.push_back(i);
          if (z[i]) {
            nodes.push_back(i);
          }
        } else {
          if (!z[i]) {
            keep.push_back(i);
            nodes.push_back(i);
          }
        }
      }
 
      vector<bool> win = winstate(keep, nodes);
 
      if (player == 0) {
        keep.clear();
        for (int i = 0; i < n; i++) {
          if (owned[i] == player) {
            keep.push_back(i);
          }
        }
      }
 
      get_win(keep, win);
      for (int i = 0; i < n; i++) {
        if (win[i]) {
          ret[i] = player;
        } else {
          ret[i] = player ^ 1;
        }
      }
 
    }
  }
  return ret;
 
  while (true) {
    vector<bool> Ze(n);
    function<void(int)> dfs = [&](int v) {
      for (int i : Rev[v]) {
        if (ret[i] != -1) {
          continue;
        }
        if (Ze[i] || owned[i] == 0) {
          continue;
        }
        Ze[i] = true;
        dfs(i);
      }
    };
    for (int i = 0; i < n; i++) {
      if (!Ze[i] && z[i] && ret[i] == -1) {
        dfs(i);
      }
    }
 
    vector<bool> removed(n);
    vector<int> que;
    vector<int> deg(n);
    for (int i = 0; i < n; i++) {
      if (ret[i] != -1) {
        continue;
      }
      for (int j : g[i]) {
        if (ret[j] == -1) {
          deg[i]++;
        }
      }
    }
 
    for (int i = 0; i < n; i++) {
      if (ret[i] != -1) {
        continue;
      }
      if (Ze[i] || z[i]) {
        removed[i] = true;
        que.push_back(i);
      }
    }
 
    for (int b = 0; b < (int) que.size(); b++) {
      int v = que[b];
      for (int i : Rev[v]) {
        if (ret[i] != -1) {
          continue;
        }
        deg[i]--;
        if (removed[i]) {
          continue;
        }
        if (owned[i] == 1 || deg[i] == 0) {
          que.push_back(i);
          removed[i] = 1;
        }
      }
    }
 
    function<void(int)> dfs1 = [&](int v) {
      for (int i : Rev[v]) {
        if (ret[i] == -1 && owned[i] == 0 && removed[i]) {
          ret[i] = 0;
          dfs1(i);
        }
      }
    };
 
    bool change = false;
    for (int i = 0; i < n; i++) {
      if (ret[i] == -1 && !removed[i]) {
        ret[i] = 0;
        change = true;
        dfs1(i);
      }
    }
 
    if (!change) {
      break;
    }
 
  }
 
  for (int i = 0; i < n; i++) {
    if (ret[i] == -1) {
      ret[i] = 1;
    }
  }
  return ret;
}

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	25 ms	49620 KB	3rd lines differ - on the 14th token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	212 KB	3rd lines differ - on the 2nd token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	250 ms	99740 KB	Output is correct
2	Correct	252 ms	99700 KB	Output is correct
3	Correct	234 ms	99680 KB	Output is correct
4	Correct	1157 ms	99700 KB	Output is correct
5	Correct	914 ms	99696 KB	Output is correct
6	Correct	634 ms	99624 KB	Output is correct
7	Correct	551 ms	99408 KB	Output is correct
8	Correct	377 ms	99564 KB	Output is correct
9	Correct	342 ms	99408 KB	Output is correct
10	Correct	447 ms	99440 KB	Output is correct
11	Correct	383 ms	99316 KB	Output is correct
12	Correct	70 ms	99348 KB	Output is correct
13	Correct	1210 ms	99720 KB	Output is correct
14	Correct	1150 ms	99640 KB	Output is correct
15	Correct	1189 ms	99688 KB	Output is correct
16	Correct	1174 ms	99728 KB	Output is correct
17	Correct	1161 ms	99620 KB	Output is correct
18	Correct	413 ms	99448 KB	Output is correct