Submission #622736

#	Time	Username	Problem	Language	Result	Execution time	Memory
622736		stoyan_malinin	Werewolf (IOI18_werewolf)	C++14	100 / 100	816 ms	133836 KiB

werewolf

#include "werewolf.h"
//#include "grader.cpp"

#include <vector>
#include <cstring>
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

const int MAXN = 2e5 + 5;
const int MAXLog = 18;

struct Event
{
    int type;
    int pos;

    int y;
    int y1, y2, ind;

    Event(){}
    Event(int type, int pos, int y)
    {
        this->type = type;
        this->pos = pos;
        this->y = y;
    }
    Event(int type, int pos, int y1, int y2, int ind)
    {
        this->type = type;
        this->pos = pos;
        this->ind = ind;
        this->y1 = y1;
        this->y2 = y2;
    }
};

struct DSU
{
    int parent[MAXN];

    DSU(){}
    DSU(int n)
    {
        for(int i = 0;i<n;i++)
            this->parent[i] = i;
    }

    int Find(int x)
    {
        if(parent[x]==x) return x;

        parent[x] = Find(parent[x]);
        return parent[x];
    }

    void Union(int u, int v)
    {
        u = Find(u);
        v = Find(v);
        if(u==v) return;

        parent[v] = u;
    }
};

struct Tree
{
    int n;
    DSU dsu;
    vector <int> graph[MAXN];

    int parent[25][MAXN];
    vector <int> order, invOrder;
    int treeSize[MAXN], orderPos[MAXN];

    Tree(){}
    Tree(int n)
    {
        this->n = n;
        this->dsu = DSU(n);
    }

    void addEdge(int u, int v)
    {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    void DFS(int x, int last)
    {
        orderPos[x] = order.size();
        order.push_back(x);

        treeSize[x] = 1;
        parent[0][x] = last;

        for(int y: graph[x])
        {
            if(y==last) continue;

            DFS(y, x);
            treeSize[x] += treeSize[y];
        }
    }

    void init(int root)
    {
        DFS(root, -1);
        for(int step = 1;step<=MAXLog;step++)
        {
            for(int x = 0;x<n;x++)
            {
                if(parent[step-1][x]==-1)
                    parent[step][x] = -1;
                else
                    parent[step][x] = parent[step-1][ parent[step-1][x] ];
            }
        }

        invOrder.resize(order.size());
        for(int i = 0;i<order.size();i++) invOrder[ order[i] ] = i;
    }
};

struct FenwickTree
{
    int n;
    int tree[MAXN];

    FenwickTree(){}
    FenwickTree(int n)
    {
        this->n = n;
        memset(this->tree, 0, sizeof(this->tree));
    }

    void update(int ind, int change)
    {
        ind++;
        while(ind<=n)
        {
            tree[ind] += change;
            ind += ind&(-ind);
        }
    }

    int query(int ind)
    {
        ind++;
        int sum = 0;

        while(ind>0)
        {
            sum += tree[ind];
            ind -= ind&(-ind);
        }

        return sum;
    }

    int query(int l, int r)
    {
        return query(r) - query(l-1);
    }
};

int n;
vector <int> graph[MAXN];

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<X.size();i++)
    {
        graph[ X[i] ].push_back(Y[i]);
        graph[ Y[i] ].push_back(X[i]);
    }

    Tree Tv(n);
    for(int x = 0;x<n;x++)
    {
        for(int y: graph[x])
        {
            if(y>=x) continue;

            int xPar = Tv.dsu.Find(x);
            int yPar = Tv.dsu.Find(y);
            if(xPar==yPar) continue;

            Tv.addEdge(xPar, yPar);
            Tv.dsu.Union(x, y);
        }
    }
    Tv.init(n-1);

    Tree Tu(n);
    for(int x = n-1;x>=0;x--)
    {
        for(int y: graph[x])
        {
            if(y<=x) continue;

            int xPar = Tu.dsu.Find(x);
            int yPar = Tu.dsu.Find(y);
            if(xPar==yPar) continue;

            Tu.addEdge(xPar, yPar);
            Tu.dsu.Union(x, y);
        }
    }
    Tu.init(0);

    vector <Event> v;
    for(int i = 0;i<Tu.order.size();i++)
    {
        v.push_back(Event(1, i, Tv.invOrder[ Tu.order[i] ]));
    }
    for(int i = 0;i<S.size();i++)
    {
        int s = S[i], e = E[i];
        int l = L[i], r = R[i];

        for(int step = MAXLog;step>=0;step--)
        {
            if(Tu.parent[step][s]!=-1 && Tu.parent[step][s]>=l) s = Tu.parent[step][s];
            if(Tv.parent[step][e]!=-1 && Tv.parent[step][e]<=r) e = Tv.parent[step][e];
        }

        pair <int, int> seg1 = {Tu.orderPos[s], Tu.orderPos[s]+Tu.treeSize[s]-1};
        pair <int, int> seg2 = {Tv.orderPos[e], Tv.orderPos[e]+Tv.treeSize[e]-1};

        v.push_back(Event(0, seg1.first, seg2.first, seg2.second, i));
        v.push_back(Event(2, seg1.second, seg2.first, seg2.second, i));
    }
    sort(v.begin(), v.end(),
    [&](Event A, Event B)
    {
        if(A.pos!=B.pos) return A.pos<B.pos;
        return A.type<B.type;
    });

    vector <int> queryAnswers, inRect;
    queryAnswers.assign(S.size(), 0);
    inRect.assign(S.size(), 0);

    FenwickTree ft(n);
    for(Event e: v)
    {
        if(e.type==0)
        {
            inRect[e.ind] -= ft.query(e.y1, e.y2);
        }
        else if(e.type==1)
        {
            ft.update(e.y, +1);
        }
        else if(e.type==2)
        {
            inRect[e.ind] += ft.query(e.y1, e.y2);
        }
    }

    for(int i = 0;i<S.size();i++)
    {
        if(inRect[i]>0) queryAnswers[i] = 1;
        else queryAnswers[i] = 0;
    }

    return queryAnswers;
}

Compilation message (stderr)

werewolf.cpp: In member function 'void Tree::init(int)':
werewolf.cpp:125:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         for(int i = 0;i<order.size();i++) invOrder[ order[i] ] = i;
      |                       ~^~~~~~~~~~~~~
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:179:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |     for(int i = 0;i<X.size();i++)
      |                   ~^~~~~~~~~
werewolf.cpp:220:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  220 |     for(int i = 0;i<Tu.order.size();i++)
      |                   ~^~~~~~~~~~~~~~~~
werewolf.cpp:224:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |     for(int i = 0;i<S.size();i++)
      |                   ~^~~~~~~~~
werewolf.cpp:269:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  269 |     for(int i = 0;i<S.size();i++)
      |                   ~^~~~~~~~~
werewolf.cpp:84:19: warning: '<anonymous>' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |         this->dsu = DSU(n);
      |         ~~~~~~~~~~^~~~~~~~
werewolf.cpp:84:19: warning: '<anonymous>' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |         this->dsu = DSU(n);
      |         ~~~~~~~~~~^~~~~~~~

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