oj.uz

Submission #73173

# Submission time Handle Problem Language Result Execution time Memory
73173 2018-08-28T02:35:57 Z funcsr Toy Train (IOI17_train) C++17
22 / 100
 694 ms 5524 KB 
#include "train.h"
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <cassert>
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define INF (1LL<<60)
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> P;

int N, M;
vector<int> G[5000], R[5000];

vector<int> who_wins(vector<int> owner, vector<int> color, vector<int> U, vector<int> V) {
  N = owner.size(), M = U.size();
  vector<int> used(N);
  rep(i, M) G[U[i]].pb(V[i]), R[V[i]].pb(U[i]);
  bool allA = true, allB = true;
  for (int x : owner) if (x == 0) allA = false; else allB = false;
  queue<int> win;
  if (allA) {
    rep(s, N) if (color[s] == 1) {
      rep(x, N) used[x] = false;
      queue<int> q;
      q.push(s);
      while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int t : G[x]) if (!used[t]) {
          used[t] = true;
          q.push(t);
        }
      }
      if (used[s]) win.push(s);
    }
  }
  else if (allB) {
    rep(s, N) if (color[s] == 0) {
      rep(x, N) used[x] = false;
      queue<int> q;
      q.push(s);
      while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int t : G[x]) if (color[t] == 0 && !used[t]) {
          used[t] = true;
          q.push(t);
        }
      }
      if (used[s]) win.push(s);
    }
  }
  else abort();
  rep(i, N) used[i] = false;

  while (!win.empty()) {
    int x = win.front(); win.pop();
    if (used[x]) continue;
    used[x] = true;
    for (int t : R[x]) win.push(t);
  }
  if (allB) rep(i, N) used[i] ^= 1;
  return used;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 1912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2016 KB Output is correct
2 Correct 37 ms 2208 KB Output is correct
3 Correct 62 ms 2216 KB Output is correct
4 Correct 305 ms 2216 KB Output is correct
5 Correct 51 ms 2216 KB Output is correct
6 Correct 90 ms 2216 KB Output is correct
7 Correct 292 ms 2228 KB Output is correct
8 Correct 12 ms 2228 KB Output is correct
9 Correct 10 ms 2228 KB Output is correct
10 Correct 14 ms 2228 KB Output is correct
11 Correct 11 ms 2228 KB Output is correct
12 Correct 10 ms 2228 KB Output is correct
13 Correct 13 ms 2228 KB Output is correct
14 Correct 12 ms 2248 KB Output is correct
15 Correct 14 ms 2248 KB Output is correct
16 Correct 13 ms 2248 KB Output is correct
17 Correct 13 ms 2248 KB Output is correct
18 Correct 164 ms 2248 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2248 KB Output is correct
2 Correct 147 ms 2248 KB Output is correct
3 Correct 254 ms 2528 KB Output is correct
4 Correct 65 ms 2732 KB Output is correct
5 Correct 474 ms 2932 KB Output is correct
6 Correct 402 ms 3148 KB Output is correct
7 Correct 374 ms 3372 KB Output is correct
8 Correct 183 ms 3516 KB Output is correct
9 Correct 12 ms 3640 KB Output is correct
10 Correct 17 ms 3824 KB Output is correct
11 Correct 22 ms 4036 KB Output is correct
12 Correct 17 ms 4244 KB Output is correct
13 Correct 694 ms 4580 KB Output is correct
14 Correct 391 ms 4912 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 5524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 1912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -