Submission #1198114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198114		badge881	Werewolf (IOI18_werewolf)	C++20	100 / 100	501 ms	85040 KiB

werewolf

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

using namespace std;

int const MAX = 2e5 + 5;
vector<int> sons[2 * MAX];
set<int> nodes[MAX];
int n;
vector<int> qL[MAX], qR[MAX];
vector<int> G[MAX];
int nod_inter[MAX];
int st[2 * MAX], dr[2 * MAX];

struct UFD
{
    int tata[2 * MAX];
    int id;
    void init()
    {
        int i;
        for (i = 0; i < 2 * n; ++i)
            tata[i] = i;
        id = n - 1;
    }
    int root(int nod)
    {
        if (tata[nod] == nod)
            return nod;
        return tata[nod] = root(tata[nod]);
    }
    void uneste1(int u, int v)
    {
        u = root(u);
        v = root(v);
        if (u != v)
        {
            ++id;
            sons[id].push_back(u);
            sons[id].push_back(v);
            tata[u] = id;
            tata[v] = id;
        }
    }
    void uneste2(int u, int v)
    {
        u = root(u);
        v = root(v);
        if (u != v)
        {
            if (nodes[u].size() < nodes[v].size())
                swap(u, v);
            tata[v] = u;
            for (auto elem : nodes[v])
                nodes[u].insert(elem);
            nodes[v].clear();
        }
    }
} ufd;

void dfs(int nod)
{
    static int time = 0;
    st[nod] = time;
    for (auto fiu : sons[nod])
        dfs(fiu);
    if (sons[nod].empty())
        ++time;
    dr[nod] = time - 1;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
    int q = S.size();
    int m = X.size();
    n = N;
    int i;
    for (i = 0; i < q; ++i)
    {
        qL[L[i]].push_back(i);
        qR[R[i]].push_back(i);
    }
    for (i = 0; i < m; ++i)
    {
        G[X[i]].push_back(Y[i]);
        G[Y[i]].push_back(X[i]);
    }
    ufd.init();
    for (i = n - 1; i >= 0; --i)
    {
        for (auto vec : G[i])
            if (vec > i)
                ufd.uneste1(i, vec);
        for (auto qry : qL[i])
            nod_inter[qry] = ufd.root(S[qry]);
    }
    dfs(ufd.id);
    ufd.init();
    for (i = 0; i < n; ++i)
        nodes[i].insert(st[i]);
    vector<int> ans(q);
    for (i = 0; i < n; ++i)
    {
        for (auto vec : G[i])
            if (vec < i)
                ufd.uneste2(vec, i);
        for (auto qry : qR[i])
        {
            int pos = E[qry];
            int rt = ufd.root(pos);
            int intv = nod_inter[qry];
            auto it = nodes[rt].lower_bound(st[intv]);
            if (it != nodes[rt].end() && *it <= dr[intv])
                ans[qry] = 1;
            else
                ans[qry] = 0;
        }
    }
    return ans;
}

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