Submission #296980

#	Time	Username	Problem	Language	Result	Execution time	Memory
296980		Aldas25	Werewolf (IOI18_werewolf)	C++14	0 / 100	4024 ms	14200 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1,(n))
#define f first
#define s second
#define pb push_back
typedef vector<int> vi;
typedef pair<int, int> pii;

const int MAXN = 200100;

int par[2*MAXN];
int find (int a) {return par[a] = par[a]==a ? a : find(par[a]);}
bool same (int a, int b) {return find(a) == find(b);}
void unite (int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    par[b] = a;
}

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) {
    int Q = S.size();
    int m = (int)X.size();
    std::vector<int> A(Q);
    for (int i = 0; i < Q; ++i) {
        FOR(j, 0, n-1) FOR(k, 0, 1) par[k*n + j] = k*n + j;
        FOR(j, L[i], R[i]) unite(j, n+j);
        //FOR(j, L[i], R[i]) cout <<" uniting " << j << ", " << n+j << endl;
        FOR(j, 0, m-1) {
            int u = X[j], v = Y[j];
            if (u > v) swap(u, v);
            if (u >= L[i]) unite(u, v);
           // if (u >= L[i]) cout << " uniting " << u << ", " << v << endl;
            if (v <= R[i]) unite(n+u,n+v);
           // if (v <= R[i]) cout << " uniting " << n+u << ", " << n+v << endl;
        }
        A[i] = same(S[i], n+E[i]);
        //cout << "  ans: " << A[i] << endl;
    }
    return A;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51