답안 #417839

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
417839 2021-06-04T11:41:32 Z Hegdahl 장난감 기차 (IOI17_train) C++17
11 / 100
13 ms 2124 KB
#include <bits/stdc++.h>
#include "train.h"

using namespace std;

const int mxN = 5000;
vector<int> g[mxN], gp[mxN], condensed[mxN];
int a[mxN], r[mxN];

bool all_a = true, all_b = true;

int vis[mxN], scc[mxN];
vector<int> order;
void dfs1(int cur) {
  vis[cur] = 1;
  for (int nxt : g[cur])
    if (!vis[nxt])
      dfs1(nxt);
  order.push_back(cur);
}

void dfs2(int root, int cur) {
  vis[cur] = 1;
  scc[cur] = root;
  for (int nxt : gp[cur])
    if (!vis[nxt])
      dfs2(root, nxt);
}

vector<int> who_wins(vector<int> _a, vector<int> _r, vector<int> u, vector<int> v) {
  const int n = (int)_a.size();
  const int m = (int)u.size();

  for (int i = 0; i < n; ++i)
    a[i] = _a[i];
  for (int i = 0; i < n; ++i)
    r[i] = _r[i];

  for (int i = 0; i < n; ++i) {
    all_a &= a[i];
    all_b &= !a[i];
  }
  assert(all_a);

  for (int i = 0; i < n; ++i)
    g[i].clear();
  for (int i = 0; i < n; ++i)
    gp[i].clear();
  for (int mm = 0; mm < m; ++mm)
    g[u[mm]].push_back(v[mm]);
  for (int mm = 0; mm < m; ++mm)
    gp[v[mm]].push_back(u[mm]);

  fill(vis, vis+n, 0);
  for (int i = 0; i < n; ++i)
    if (!vis[i])
      dfs1(i);
  reverse(order.begin(), order.end());
  fill(vis, vis+n, 0);
  for (int i : order)
    if (!vis[i])
      dfs2(i, i);

  /*
  cerr << "scc: ";
  for (int i = 0; i < n; ++i)
    cerr << scc[i] << " \n"[i==n-1]; // */

  vector<int> e_cnt(n), ans(n);
  for (int mm = 0; mm < m; ++mm)
    e_cnt[scc[u[mm]]] += scc[u[mm]] == scc[v[mm]];

  /*
  cerr << "e_cnt: ";
  for (int i = 0; i < n; ++i)
    cerr << e_cnt[i] << " \n"[i==n-1]; // */

  for (int i = 0; i < n; ++i)
    ans[scc[i]] |= e_cnt[scc[i]] && r[i];

  /*
  cerr << "scc_ans: ";
  for (int i = 0; i < n; ++i)
    cerr << ans[i] << " \n"[i==n-1]; // */

  for (int mm = 0; mm < m; ++mm)
    condensed[scc[u[mm]]].push_back(scc[v[mm]]);

  reverse(order.begin(), order.end());
  for (int i : order) {
    if (scc[i] != i) continue;
    for (int j : condensed[i])
      ans[scc[i]] |= ans[scc[j]];
  }

  for (int i = 0; i < n; ++i)
    ans[i] = ans[scc[i]];

  return ans;
}
# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 1612 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1100 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 1996 KB Output is correct
2 Correct 9 ms 2080 KB Output is correct
3 Correct 9 ms 2120 KB Output is correct
4 Correct 10 ms 1996 KB Output is correct
5 Correct 10 ms 1996 KB Output is correct
6 Correct 10 ms 1868 KB Output is correct
7 Correct 10 ms 1856 KB Output is correct
8 Correct 9 ms 1960 KB Output is correct
9 Correct 9 ms 1868 KB Output is correct
10 Correct 9 ms 1816 KB Output is correct
11 Correct 9 ms 1852 KB Output is correct
12 Correct 9 ms 1780 KB Output is correct
13 Correct 10 ms 2104 KB Output is correct
14 Correct 10 ms 2124 KB Output is correct
15 Correct 10 ms 2076 KB Output is correct
16 Correct 13 ms 2124 KB Output is correct
17 Correct 9 ms 2124 KB Output is correct
18 Correct 11 ms 1660 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 1868 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 1996 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 1612 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -