Submission #282035

#	Time	Username	Problem	Language	Result	Execution time	Memory
282035		stoyan_malinin	Werewolf (IOI18_werewolf)	C++14	15 / 100	701 ms	72044 KiB

werewolf

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

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

using namespace std;

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

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

bool solveDP(int s, int e, int l, int r)
{
    if(s<l || e>r) return false;

    vector <bool> used[2];
    used[0].assign(n+5, false);
    used[1].assign(n+5, false);

    function <void(int, int)> DFS = [&](int x, int state)
    {
        if(used[state][x]==true) return;
        used[state][x] = true;

        //cout << state << " " << x << '\n';

        if(state==0 && x>=l && x<=r) DFS(x, 1);
        for(int y: graph[x])
        {
            if(state==0 && y<l) continue;
            if(state==1 && y>r) continue;

            DFS(y, state);
        }
    };

    DFS(s, 0);
    return used[1][e];
}

struct Element
{
    int minVal, maxVal;

    Element(){}
    Element(int x)
    {
        this->minVal = x;
        this->maxVal = x;
    }
};

Element Merge(Element A, Element B)
{
    Element out;
    out.minVal = min(A.minVal, B.minVal);
    out.maxVal = max(A.maxVal, B.maxVal);

    return out;
}

int orderPos[MAXN];
vector <int> dfsOrder;

int logVal[MAXN];
Element sparse[20][MAXN];

void initLine()
{
    int root = -1;
    for(int x = 0;x<n;x++)
    {
        if(graph[x].size()==1)
        {
            root = x;
            break;
        }
    }

    function <void(int, int)> DFS = [&](int x, int last)
    {
        orderPos[x] = dfsOrder.size();
        dfsOrder.push_back(x);

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

    DFS(root, -1);
    for(int i = 0;i<n;i++) sparse[0][i] = Element(dfsOrder[i]);
    for(int i = 1;i<=MAXLog;i++)
    {
        for(int j = 0;j<n;j++)
        {
            if(j+(1<<(i-1))<n)
                sparse[i][j] = Merge(sparse[i-1][j], sparse[i-1][j+(1<<(i-1))]);
            else
                sparse[i][j] = sparse[i-1][j];
        }
    }

    logVal[0] = logVal[1] = 0;
    for(int i = 2;i<=n;i++) logVal[i] = logVal[i/2] + 1;
}

Element getSegment(int l, int r)
{
    int log2 = logVal[r-l+1];
    return Merge(sparse[log2][l], sparse[log2][r-(1<<log2)+1]);
}

bool solveLine1(int S, int E, int L, int R)
{
    if(S<L || E>R) return false;

    int sPos = orderPos[S];
    int ePos = orderPos[E];
    int ind1, ind2;

    assert(sPos<ePos);

    int l = sPos, r = ePos, mid;
    while(l+1<r)
    {
        mid = (l+r)/2;

        if(getSegment(sPos, mid).minVal>=L) l = mid;
        else r = mid - 1;
    }
    if(getSegment(sPos, r).minVal>=L) ind1 = r;
    else if(getSegment(sPos, l).minVal>=L) ind1 = l;

    l = sPos, r = ePos, mid;
    while(l+1<r)
    {
        mid = (l+r)/2;

        if(getSegment(mid, ePos).maxVal<=R) r = mid;
        else l = mid + 1;
    }
    if(getSegment(l, ePos).maxVal<=R) ind2 = l;
    else if(getSegment(r, ePos).maxVal<=R) ind2 = r;

    cout << ind1 << " " << ind2 << '\n';
    return (ind1>=ind2);
}

bool solveLine2(int S, int E, int L, int R)
{
    swap(S, E);
    if(S>R || E<L) return false;

    int sPos = orderPos[S];
    int ePos = orderPos[E];
    int ind1, ind2;

    int l = sPos, r = ePos, mid;
    while(l+1<r)
    {
        mid = (l+r)/2;

        if(getSegment(sPos, mid).minVal<=R) l = mid;
        else r = mid - 1;
    }
    if(getSegment(sPos, r).minVal<=R) ind1 = r;
    else if(getSegment(sPos, l).minVal<=R) ind1 = l;

    l = sPos, r = ePos, mid;
    while(l+1<r)
    {
        mid = (l+r)/2;

        if(getSegment(mid, ePos).maxVal>=L) r = mid;
        else l = mid + 1;
    }
    if(getSegment(l, ePos).maxVal>=L) ind2 = l;
    else ind2 = r;

    cout << ind1 << " " << ind2 << '\n';
    return (ind1>=ind2);
}

bool solveLine(int S, int E, int L, int R)
{
    if(orderPos[S]<orderPos[E]) return solveLine1(S, E, L, R);
    return solveLine2(S, E, L, R);
}


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]);
    }

    vector <int> queryAnswers;

    if(n<=6000 && X.size()<=6000 && S.size())
    {
        for(int i = 0;i<S.size();i++)
        {
            queryAnswers.push_back(solveDP(S[i], E[i], L[i], R[i]));
        }
    }
    else
    {
        initLine();
        for(int i = 0;i<S.size();i++)
        {
            queryAnswers.push_back(solveLine(S[i], E[i], L[i], R[i]));
        }
    }

    return queryAnswers;
}
/*
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

6 5 2
0 2
2 1
1 5
5 4
4 3
0 1 0 2
1 0 1 2

*0 2 1 5 4 3
*/

Compilation message (stderr)

werewolf.cpp: In function 'bool solveLine1(int, int, int, int)':
werewolf.cpp:141:28: warning: right operand of comma operator has no effect [-Wunused-value]
  141 |     l = sPos, r = ePos, mid;
      |                            ^
werewolf.cpp: In function 'bool solveLine2(int, int, int, int)':
werewolf.cpp:176:28: warning: right operand of comma operator has no effect [-Wunused-value]
  176 |     l = sPos, r = ePos, mid;
      |                            ^
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:203:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  203 |     for(int i = 0;i<X.size();i++)
      |                   ~^~~~~~~~~
werewolf.cpp:213:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |         for(int i = 0;i<S.size();i++)
      |                       ~^~~~~~~~~
werewolf.cpp:221:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  221 |         for(int i = 0;i<S.size();i++)
      |                       ~^~~~~~~~~
werewolf.cpp: In function 'bool solveLine2(int, int, int, int)':
werewolf.cpp:187:21: warning: 'ind1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  187 |     cout << ind1 << " " << ind2 << '\n';
      |                     ^~~

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