제출 #568542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568542		ngpin04	늑대인간 (IOI18_werewolf)	C++17	0 / 100	420 ms	54724 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
  return l + rd() % (r - l + 1);
}
const int N = 4e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

struct DSU {
    bool rev;
    int n;
    vector <int> par,val;

    DSU(int _n = 0, bool _rev = 0) {
        rev = _rev;
        n = _n;
        par.assign(n + 5, -1);
        val.assign(n + 5, 0);
        iota(ALL(val), 0);
    }

    int getpar(int u) {
        return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
    }

    void join(int u, int v) {
        u = getpar(u);
        v = getpar(v);
        if (par[u] > par[v])
            swap(u, v);
        if (u == v)
            return;
        par[u] += par[v];
        par[v] = u;
        if (!rev)
            maxi(val[u], val[v]);
        else
            mini(val[u], val[v]);
    }    

    int getval(int u) {
        return val[getpar(u)];
    }
};

vector <int> ed[N];
vector <int> qr[N];

int par[N];
int ans[N];
int mx[N];
int x[N];
int y[N];
int s[N];
int t[N];
int l[N];
int r[N];
int n,q;

void fix() {
    for (int i = 0; i < n; i++)
        ed[i].clear(), qr[i].clear();

    for (int i = 0; i < n - 1; i++) 
        ed[y[i]].push_back(x[i]);

    for (int i = 0; i < q; i++)
        qr[r[i]].push_back(i);

    DSU pre(n, 0);
    for (int i = 0; i < n; i++) {
        for (int j : ed[i])
            pre.join(i, j);

        for (int ind : qr[i]) 
            t[ind] = pre.getval(t[ind]);
    }

    for (int i = 0; i < n; i++)
        ed[i].clear(), qr[i].clear();

    for (int i = 0; i < n - 1; i++) 
        ed[x[i]].push_back(y[i]);

    for (int i = 0; i < q; i++)
        qr[l[i]].push_back(i);

    DSU suf(n, 1);
    for (int i = n - 1; i >= 0; i--) {
        for (int j : ed[i])
            suf.join(i, j);

        for (int ind : qr[i]) 
            s[ind] = suf.getval(s[ind]);
    }
}

void getans() {
    for (int i = 0; i < n; i++)
        ed[i].clear(), qr[i].clear();

    for (int i = 0; i < n - 1; i++) 
        ed[y[i]].push_back(x[i]);

    for (int i = 0; i < q; i++)
        qr[r[i]].push_back(i);

    DSU pre(n, 0);
    for (int i = 0; i < n; i++) {
        for (int j : ed[i])
            pre.join(i, j);

        for (int ind : qr[i]) {
            if (t[ind] < l[ind] || s[ind] > r[ind])
                continue;
            ans[ind] |= pre.getpar(t[ind]) == pre.getpar(s[ind]);
        }
    }

    for (int i = 0; i < n; i++)
        ed[i].clear(), qr[i].clear();

    for (int i = 0; i < n - 1; i++) 
        ed[x[i]].push_back(y[i]);

    for (int i = 0; i < q; i++)
        qr[l[i]].push_back(i);

    DSU suf(n, 1);
    for (int i = n - 1; i >= 0; i--) {
        for (int j : ed[i])
            suf.join(i, j);

        for (int ind : qr[i]) {
            if (t[ind] < l[ind] || s[ind] > r[ind])
                continue;
            ans[ind] |= suf.getpar(t[ind]) == suf.getpar(s[ind]);
        }
    }
}

void solve() {
    for (int i = 0; i < n - 1; i++) 
        if (x[i] > y[i])
            swap(x[i], y[i]);

    fix();
    getans();
}   

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
    n = N;
    for (int i = 0; i < n - 1; i++)
        x[i] = X[i], y[i] = Y[i];

    q = S.size();
    for (int i = 0; i < q; i++) {
        s[i] = S[i];
        t[i] = E[i];
        l[i] = L[i];
        r[i] = R[i];
    }

    solve();
    vector <int> res;
    for (int i = 0; i < q; i++)
        res.push_back(ans[i]);
    return res;
}

//#include "grader.cpp"

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