Submission #382989

#	Time	Username	Problem	Language	Result	Execution time	Memory
382989		mohamedsobhi777	Werewolf (IOI18_werewolf)	C++14	15 / 100	871 ms	24448 KiB

werewolf

#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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51