oj.uz

Submission #835137

# Submission time Handle Problem Language Result Execution time Memory
835137 2023-08-23T09:00:37 Z Johann Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 26360 KB 
#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N, Q, M;
vvi adj;
vi S, E, L, R;

struct unionfind
{
  vi arr;
  void init(int size)
  {
    arr.resize(size);
    iota(all(arr), 0);
  }
  int find(int i) { return arr[i] = (arr[i] == i) ? i : find(arr[i]); }
  void combine(int a, int b)
  {
    a = find(a), b = find(b);
    arr[a] = b;
  }
};

std::vector<int> check_validity(int _N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> _S, std::vector<int> _E,
                                std::vector<int> _L, std::vector<int> _R)
{
  N = _N, Q = sz(_S), M = sz(X);
  S = _S, E = _E, L = _L, R = _R;
  adj.clear();
  adj.resize(N);
  for (int i = 0; i < M; ++i)
    adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);

  std::vector<int> A(Q);
  for (int q = 0; q < Q; ++q)
  {
    unionfind ufHuman, ufWolf;
    ufHuman.init(N), ufWolf.init(N);
    for (int i = 0; i < M; ++i)
      if (X[i] >= L[q] && Y[i] >= L[q])
        ufHuman.combine(X[i], Y[i]);
    for (int i = 0; i < M; ++i)
      if (X[i] <= R[q] && Y[i] <= R[q])
        ufWolf.combine(X[i], Y[i]);
    A[q] = 0;
    for (int i = 0; i < N; ++i)
      A[q] |= (ufHuman.find(S[q]) == ufHuman.find(i) && ufWolf.find(E[q]) == ufWolf.find(i));
  }
  return A;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 392 ms 776 KB Output is correct
11 Correct 320 ms 772 KB Output is correct
12 Correct 227 ms 768 KB Output is correct
13 Correct 356 ms 796 KB Output is correct
14 Correct 255 ms 788 KB Output is correct
15 Correct 749 ms 880 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4042 ms 26360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 392 ms 776 KB Output is correct
11 Correct 320 ms 772 KB Output is correct
12 Correct 227 ms 768 KB Output is correct
13 Correct 356 ms 796 KB Output is correct
14 Correct 255 ms 788 KB Output is correct
15 Correct 749 ms 880 KB Output is correct
16 Execution timed out 4042 ms 26360 KB Time limit exceeded
17 Halted 0 ms 0 KB -