Submission #417839

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
417839	2021-06-04T11:41:32 Z	Hegdahl	Toy Train (IOI17_train)	C++17	11 / 100	13 ms	2124 KB

train

#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;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	6 ms	1612 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	2 ms	1100 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	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