Submission #253592

#	Time	Username	Problem	Language	Result	Execution time	Memory
253592		emil_physmath	Werewolf (IOI18_werewolf)	C++17	100 / 100	1072 ms	174572 KiB

werewolf

#include "werewolf.h"
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int maxN = 200'005;
struct Quer {
    int l, r, s, e, ind, link1, link2;
};

int n;
vector<int> ans;
vector<Quer> quer, withLink1[maxN * 2];
vector<int> nei[maxN], nei1[maxN * 2], nei2[maxN * 2];
set<int> t[maxN * 2];
int col[maxN], linkl[maxN * 2], linkr[maxN * 2];

struct DSU
{
    vector<int> par, sz, link;
    DSU(int n)
        : par(n)
        , sz(n)
        , link(n)
    {
        for (int i = 0; i < n; ++i)
            par[i] = link[i] = i, sz[i] = 1;
    }
    int root(int v) {
        return v == par[v] ? v : par[v] = root(par[v]);
    }
    void unite(int u, int v, int curLink) {
        u = root(u); v = root(v);
        if (u == v) return;
        if (sz[u] > sz[v]) swap(u, v);
        sz[v] += sz[u];
        par[u] = v;
        link[v] = curLink;
    }
};
void DFS(int v)
{
    static int time = -1;
    linkl[v] = time + 1;
    if (nei2[v].empty())
        col[v] = ++time;
    for (int to: nei2[v])
    {
        // cerr << v << " -> " << to << '\n';
        DFS(to);
    }
    linkr[v] = time;
}
int Color1()
{
    DSU dsu(n);
    int nodes = n;
    sort(quer.begin(), quer.end(), [](const Quer& l, const Quer& r) {
        return l.l < r.l;
    });
    for (int v = n - 1, i = (int)quer.size() - 1; v >= 0; --v)
    {
        nei1[nodes].push_back(dsu.link[dsu.root(v)]);
        for (int to: nei[v])
        {
            if (to < v) continue;
            if (dsu.root(v) == dsu.root(to))
                continue;
            nei1[nodes].push_back(dsu.link[dsu.root(to)]);
            dsu.unite(v, to, nodes);
        }
        while (i >= 0 && quer[i].l == v) {
            quer[i].link1 = dsu.link[dsu.root(quer[i].s)];
            --i;
        }
        ++nodes;
    }
    return nodes - 1;
}
void Color2()
{
    DSU dsu(n);
    int nodes = n;
    sort(quer.begin(), quer.end(), [](const Quer& l, const Quer& r) {
        return l.r > r.r;
    });
    for (int v = 0, i = (int)quer.size() - 1; v < n; ++v)
    {
        int b = -1;
        nei2[nodes].push_back(b = dsu.link[dsu.root(v)]);
        for (int to: nei[v])
        {
            if (to > v) continue;
            if (dsu.root(v) == dsu.root(to))
                continue;
            nei2[nodes].push_back(b = dsu.link[dsu.root(to)]);
            dsu.unite(v, to, nodes);
        }
        while (i >= 0 && quer[i].r == v) {
            quer[i].link2 = dsu.link[dsu.root(quer[i].e)];
            --i;
        }
        ++nodes;
    }
    DFS(nodes - 1);
}
void Solve(int v)
{
    if (nei1[v].empty())
        t[v].insert(col[v]);
    for (int to: nei1[v])
    {
        Solve(to);
        if (t[v].size() < t[to].size())
            t[v].swap(t[to]);
        t[v].insert(t[to].begin(), t[to].end());
    }
    for (Quer& q: withLink1[v])
    {
        auto it = t[v].lower_bound(linkl[q.link2]);
        if (it != t[v].end() && *it <= linkr[q.link2])
            ans[q.ind] = 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) {
    n = N;
    quer.resize(S.size());
    for (int i = 0; i < S.size(); ++i)
    {
        quer[i].s = S[i];
        quer[i].e = E[i];
        quer[i].l = L[i];
        quer[i].r = R[i];
        quer[i].ind = i;
    }
    for (int i = 0; i < X.size(); ++i)
    {
        int u = X[i], v = Y[i];
        nei[u].push_back(v);
        nei[v].push_back(u);
    }
    int root = Color1();
    Color2();
    ans.resize(quer.size());
    for (Quer& q: quer)
        withLink1[q.link1].push_back(q);
    Solve(root);
    return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:131:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < S.size(); ++i)
                     ~~^~~~~~~~~~
werewolf.cpp:139:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < X.size(); ++i)
                     ~~^~~~~~~~~~

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