oj.uz

Submission #382988

# Submission time Handle Problem Language Result Execution time Memory
382988 2021-03-28T16:37:11 Z mohamedsobhi777 Werewolf (IOI18_werewolf) C++14
7 / 100
 183 ms 32784 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int N = 1000 + 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 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct

Subtask #2
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 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Runtime error 4 ms 876 KB Execution killed with signal 7
11 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 183 ms 32784 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 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Runtime error 4 ms 876 KB Execution killed with signal 7
11 Halted 0 ms 0 KB -