oj.uz

Submission #382989

# Submission time Handle Problem Language Result Execution time Memory
382989 2021-03-28T16:37:40 Z mohamedsobhi777 Werewolf (IOI18_werewolf) C++14
15 / 100
 871 ms 24448 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int N = 3000 + 7;

int n, m;
vector<int> le, ri;

struct dsu
{
       int fat[N];
       dsu()
       {
              iota(fat, fat + N, 0);
       }
       int find(int x) { return fat[x] = x == fat[x] ? x : find(fat[x]); }
       void link(int u, int v)
       {
              u = find(u), v = find(v);
              fat[u] = v;
       }
       inline bool same(int u, int v) { return find(u) == find(v); }
};

bool solve(int st, int en, int L, int R)
{
       dsu d1, d2;
       for (int i = 0; i < m; ++i)
       {
              int u = le[i], v = ri[i];
              if (max(u, v) <= R)
                     d1.link(u, v);
              if (min(u, v) >= L)
                     d2.link(u, v);
       }
       for (int i = L; i <= R; ++i)
       {
              if (d1.same(en, i) && d2.same(st, i))
                     return 1;
       }

       return 0;
}

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, m = X.size();
       le = X, ri = Y;
       int Q = S.size();
       std::vector<int> A(Q);

       for (int i = 0; i < Q; ++i)
       {
              A[i] = solve(S[i], E[i], L[i], R[i]);
       }

       return A;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 394 ms 492 KB Output is correct
11 Correct 313 ms 672 KB Output is correct
12 Correct 256 ms 620 KB Output is correct
13 Correct 394 ms 748 KB Output is correct
14 Correct 298 ms 640 KB Output is correct
15 Correct 871 ms 876 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 179 ms 24448 KB Execution killed with signal 7
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 394 ms 492 KB Output is correct
11 Correct 313 ms 672 KB Output is correct
12 Correct 256 ms 620 KB Output is correct
13 Correct 394 ms 748 KB Output is correct
14 Correct 298 ms 640 KB Output is correct
15 Correct 871 ms 876 KB Output is correct
16 Runtime error 179 ms 24448 KB Execution killed with signal 7
17 Halted 0 ms 0 KB -