Submission #96094

#	Time	Username	Problem	Language	Result	Execution time	Memory
96094		bogdan10bos	Werewolf (IOI18_werewolf)	C++14	100 / 100	1134 ms	104188 KiB

werewolf

#include "werewolf.h"

using namespace std;

typedef pair<int, int> pii;

const int NMAX = 2e5;

int N;
vector< vector<int> > edg;

class Tree
{
public:
    int N, I;
    vector<int> f, fth[20];
    vector<int> lft, rgt, ord;
    vector< vector<int> > edg;

    int F(int x)
    {
        if(f[x] == x)   return x;
        return f[x] = F(f[x]);
    }

    void init(int _N)
    {
        N = _N;
        f.resize(N + 2);
        edg.resize(N + 2);
        for(int i = 0; i < N; i++)  f[i] = i;
        lft.resize(N + 2);
        rgt.resize(N + 2);
        for(int i = 0; i < 19; i++) fth[i].resize(N + 2);
        ord.resize(N + 2);
    }

    void add(int x, int y)
    {
        int fx = F(x);
        int fy = F(y);
        if(fx == fy)    return;

        edg[fx].push_back(fy);
        f[fy] = fx;
    }

    void DFS(int nod, int f = -1)
    {
        fth[0][nod] = f;
        for(int i = 1; i < 19; i++)
        {
            if(fth[i - 1][nod] == -1)   fth[i][nod] = -1;
            else    fth[i][nod] = fth[i - 1][ fth[i - 1][nod] ];
        }

        lft[nod] = ++I;
        ord[I] = nod;
        for(auto nxt: edg[nod])
            DFS(nxt, nod);
        rgt[nod] = I;
    }
};

Tree pfx, sfx;

class BinaryIndexedTree
{
public:
    int N;
    vector<int> aib;

    void init(int _N)
    {
        N = _N;
        aib.resize(N + 2);
    }

    void U(int pos, int val)
    {
        for(; pos <= N; pos += (pos & (-pos)))
            aib[pos] += val;
    }

    int Q(int pos)
    {
        int ans = 0;
        for(; pos > 0; pos -= (pos & (-pos)))
            ans += aib[pos];
        return ans;
    }
}aib;

vector<int> check_validity(int _N, vector<int> e1, vector<int> e2,
                           vector<int> S, vector<int> T,
                           vector<int> L, vector<int> R)
{
    N = _N;
    edg.resize(N + 2);
    for(int i = 0; i < e1.size(); i++)
    {
        int x = e1[i], y = e2[i];
        edg[x].push_back(y);
        edg[y].push_back(x);
    }

    pfx.init(N);
    for(int i = 0; i < N; i++)
        for(auto nod: edg[i])
            if(nod < i)
                pfx.add(i, nod);
    pfx.DFS(N - 1);

    sfx.init(N);
    for(int i = N - 1; i >= 0; i--)
        for(auto nod: edg[i])
            if(nod > i)
                sfx.add(i, nod);
    sfx.DFS(0);

    int Q = L.size();
    vector<int> ans;
    ans.resize(Q);
    vector<pii> itv;
    itv.resize(Q + 2);
    vector< vector<int> > upd;
    upd.resize(N + 2);

    for(int i = 0; i < Q; i++)
    {
        int nod = S[i], lmt = L[i];
        for(int i = 18; i >= 0; i--)
            if(sfx.fth[i][nod] != -1 && sfx.fth[i][nod] >= lmt)
                nod = sfx.fth[i][nod];
        pii itvsfx = {sfx.lft[nod], sfx.rgt[nod]};

        nod = T[i], lmt = R[i];
        for(int i = 18; i >= 0; i--)
            if(pfx.fth[i][nod] != -1 && pfx.fth[i][nod] <= lmt)
                nod = pfx.fth[i][nod];
        pii itvpfx = {pfx.lft[nod], pfx.rgt[nod]};

        itv[i] = itvsfx;
        upd[itvpfx.first - 1].push_back( -(i + 1));
        upd[itvpfx.second].push_back(i + 1);
    }

    aib.init(N);
    for(int i = 1; i <= N; i++)
    {
        int nod = pfx.ord[i];
        aib.U(sfx.lft[nod], 1);

        for(auto id: upd[i])
        {
            int smn = 1;
            if(id < 0) smn = -1, id = -id;
            id--;

            ans[id] += smn * (aib.Q(itv[id].second) - aib.Q(itv[id].first - 1));
        }
    }

    for(int i = 0; i < Q; i++)
        if(ans[i] != 0) ans[i] = 1;
    return ans;
}

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:100:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < e1.size(); i++)
                    ~~^~~~~~~~~~~

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