Submission #208845

#	Time	Username	Problem	Language	Result	Execution time	Memory
208845		teomrn	Werewolf (IOI18_werewolf)	C++14	100 / 100	1355 ms	122664 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;

struct Aib {
    vector <int> aib;
    function <int(int)> lsb = [](int x) { return x & (-x); };
    function <int(int)> qry = [&](int p) {
        int ans = 0;
        while (p)
            ans += aib[p], p -= lsb(p);
        return ans;
    };

    Aib(int N) : aib(N + 2, 0) { }

    void Update(int poz, int val)
    {
        poz++;
        while (poz < (int)aib.size())
            aib[poz] += val, poz += lsb(poz);
    }

    int Query(int st, int dr)
    {
        st++, dr++;
        return qry(dr) - (st > 0 ? qry(st - 1) : 0);
    }
};

struct Tree {
    vector <int> stramos, liniarizare;
    vector <pair <int, int>> poz_in_liniarizare;
    vector <vector <int>> adia;
    vector <vector <int>> up;
    int root;

    Tree(int N) : stramos(N), poz_in_liniarizare(N), adia(N), up(N, vector <int> (20, -1)) {
        iota(stramos.begin(), stramos.end(), 0);
    }

    int FindStramos(int nod) {
        if (stramos[nod] != nod)
            return stramos[nod] = FindStramos(stramos[nod]);
        return stramos[nod];
    }

    void Dfs(int nod) {
        
        // cerr << "Node " << nod << " has sons ";
        // for (auto i : adia[nod])
        //     cerr << i << ' ';
        // cerr << '\n';

        for (int i = 1; i < 20; i++)
            if (up[nod][i - 1] != -1)
                up[nod][i] = up[up[nod][i - 1]][i - 1];

        poz_in_liniarizare[nod].first = liniarizare.size();
        liniarizare.push_back(nod);
        for (auto i : adia[nod])
            Dfs(i);

        poz_in_liniarizare[nod].second = liniarizare.size() - 1;
    }

    pair <int, int> Span(int nod, function <bool(int)> ok) {
        assert(ok(nod));
        for (int i = 19; i >= 0; i--)
            if (up[nod][i] != -1 && ok(up[nod][i]))
                nod = up[nod][i];

        return poz_in_liniarizare[nod];
    }
};

vector <int> check_validity(int N, vector <int> X, vector <int> Y, vector <int> S, vector <int> E, vector <int> L, vector <int> R)
{
    vector <vector <int>> graph(N);
    for (int i = 0; i < (int)X.size(); i++) {
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }

    Tree small_up(N), big_up(N);

    for (int i = 0; i < N; i++) {
        for (auto vec : graph[i]) {
            int x = big_up.FindStramos(vec);
            if (vec < i && x != i) {
                big_up.stramos[x] = i;
                big_up.up[x][0] = i;
                big_up.adia[i].push_back(x);
            }
        }
    }
    for (int i = N - 1; i >= 0; i--) {
        for (auto vec : graph[i]) {
            int x = small_up.FindStramos(vec);
            if (vec > i && x != i) {
                small_up.stramos[x] = i;
                small_up.up[x][0] = i;
                small_up.adia[i].push_back(x);
            }
        }
    }

    // cerr << "For small_up:\n";
    small_up.Dfs(0);
    // cerr << "\nFor bi_up:\n";
    big_up.Dfs(N - 1);

    // cerr << "Finished trees\n";

    /// I have built the trees, now I have to check for each node the interval it can reach

    int Q = S.size();
    vector <int> intersection(Q, 0);
    vector <pair <int, int>> to_verify(Q);
    vector <vector <pair <int, int>>> events(N + 1); // pentru fiecare pozitie daca trebuie sa scad / sa adaug raspunsul pt un query
    Aib aib(N);

    for (int i = 0; i < Q; i++) {
        auto intervS = small_up.Span(S[i], [&](int nod) -> bool { return nod >= L[i]; });
        auto intervE = big_up.Span(E[i], [&](int nod) -> bool { return nod <= R[i]; });

        // cerr << "Query i can get from S=" << S[i] << " to ";
        // for (int j = intervS.first; j <= intervS.second; j++)
        //     cerr << small_up.liniarizare[j] << ' ';
            
        // cerr << "\nQuery i can get from E=" << E[i] << " to ";
        // for (int j = intervE.first; j <= intervE.second; j++)
        //     cerr << big_up.liniarizare[j] << ' ';
        // cerr << "\n\n";
        
        to_verify[i] = intervE;
        events[intervS.first].push_back({ i, -1 });
        events[intervS.second + 1].push_back({ i, 1 });
    }

    // cerr << "Finished adding segments\n";

    for (int i = 0; i <= N; i++) {
        /// mai intai verific de e de procesat
        for (auto op : events[i]) {
            int val = aib.Query(to_verify[op.first].first, to_verify[op.first].second);
            intersection[op.first] += val * op.second;
        }

        if (i < N) {
            int elem = small_up.liniarizare[i];
            int poz_in_big = big_up.poz_in_liniarizare[elem].first;
            aib.Update(poz_in_big, 1);   
        }
    }

    for (auto & it : intersection) {
        assert(it >= 0);
        it = min(it, 1);
    }

    return intersection;
}

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