Submission #1139868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139868		elsantodel90	Werewolf (IOI18_werewolf)	C++20	34 / 100	472 ms	36308 KiB

werewolf

#include "werewolf.h"
#include <cassert>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

#define forn(i,n) for(int i=0;i<int(n);i++)

#define SIZE(c) int((c).size())
#define ALL(c) begin(c), end(c)
#define DBG(x) cerr << #x << " = " << (x) << endl

template <typename T>
ostream & operator<<(ostream &os, const vector<T> &v)
{
    os << "[";
    forn(i,SIZE(v))
    {
        if (i > 0)
            os << ",";
        os << v[i];
    }
    os << "]";
    return os;
}

const int MAXN = 210000;
const int LEVELS = 20;

int sparseTable[LEVELS][MAXN];
int neighbors[MAXN][2];
int degree[MAXN];

int rmq(int a, int b)
{
    assert(a < b);
    int potIndex = 31-__builtin_clz(b-a);
    int pot = 1 << potIndex;
    return min(sparseTable[potIndex][a], sparseTable[potIndex][b-pot]);
}

int query(int N, int s, int L) // Cuantos hay desde s que son >= L
{
    // [s, a) son todos >= L
    // [s, b) NO son todos >= L
    int a = s;
    int b = N+1;
    while (b-a > 1)
    {
        int c = (a+b)/2;
        if (rmq(s, c) >= L)
            a = c;
        else
            b = c;
    }
    assert(s < a); // Por restriccion del enunciado!
    return a-s;
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    const int M = SIZE(X);
    forn(i,N)
    forn(k,2)
        neighbors[i][k] = -1;
    forn(i, M)
    {
        #define ADD_NEIGHBOR(a,b) do {assert(degree[a] < 2); neighbors[a][degree[a]++] = (b); } while (false)
        ADD_NEIGHBOR(X[i],Y[i]);
        ADD_NEIGHBOR(Y[i],X[i]);
    }
    vector<int> nodes(N);
    forn(i, N)
    if (degree[i] == 1)
    {
        int current = i;
        int last = neighbors[current][1];
        forn(j,N)
        {
            nodes[j] = current;
            int oldCurrent = current;
            current = neighbors[current][0] ^ neighbors[current][1] ^ last;
            last = oldCurrent;
        }
        goto taTodoReBien;
    }
    assert(false);
taTodoReBien:;
    
    map<int,int> indices;
    forn(i,N)
        indices[nodes[i]] = i;
    int Q = SIZE(S);
    forn(i,Q) // TRADUZCO LA QUERIES, OJO CON EL CUADRATICO
    {
        S[i] = indices[S[i]];
        E[i] = indices[E[i]];
    }
    vector<int> ret(Q, 0);
    forn(reversedPass,2) // S < E     S > E
    {
        forn(pass,2) // S,L    N-1-E, -R, array flipeado
        {
            forn(i,N)
                sparseTable[0][i] = nodes[i];
            forn(i,LEVELS-1)
            forn(j,N-(1<<(i+1))+1)
                sparseTable[i+1][j] = min(sparseTable[i][j], sparseTable[i][j+(1<<i)]);
            forn(i,Q)
            if (S[i] < E[i])
            {
                if (pass == 0)
                    ret[i] += query(N, S[i], L[i]);
                else
                    ret[i] += query(N, N-1-E[i], -R[i]);
            }
            reverse(ALL(nodes));
            forn(i,SIZE(nodes))
                nodes[i] = -nodes[i];
        }
        reverse(ALL(nodes));
        forn(i,Q)
        {
            S[i] = N-1-S[i];
            E[i] = N-1-E[i];
        }
    }
    forn(i,Q)
        ret[i] = ret[i] > abs(E[i] - S[i])+1;
    return ret;
}

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