oj.uz

Submission #434197

# Submission time Handle Problem Language Result Execution time Memory
434197 2021-06-20T17:50:46 Z Tiago_Marques Werewolf (IOI18_werewolf) C++17
49 / 100
 784 ms 62140 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

#define REP(i, a, b) for (ll i=a; i<b; i++)
#define pb push_back

int ordem[200000];
vector<int> graph[200000];
int sparse_maximo[200000][20];
int sparse_minimo[200000][20];
int posicao[200000];
int visited[200000] = {};
queue<int> possiveis[2];

void dfs (int u, int indice, int type, int r, int l)
{
    visited[u] = indice + 1;
    for (auto v: graph[u])
    {
        if (visited[v] > indice)
            continue;
        if ((type == 0 && v >= l) || (type == 1 && v <= r && v >= l) || (type == 2 && v <= r))
        {
            if (type != 2)
                possiveis[type].push (v);
            dfs (v, indice, type, r, l);
        }
    }
}

void create (int N)
{
    for (ll i=N-1; i>=0; i--)
    {
        sparse_maximo[i][0] = ordem[i];
        sparse_minimo[i][0] = ordem[i];
        REP(j, 1, 20)
        {
            if (i + (1<<j) > N)
                break;
            sparse_maximo[i][j] = max (sparse_maximo[i][j-1], sparse_maximo[i + (1<<(j-1))][j-1]);
            sparse_minimo[i][j] = min (sparse_minimo[i][j-1], sparse_minimo[i + (1<<(j-1))][j-1]);
        }
    }
}

int maximizar (int a, int b)
{
    int i = log2(b - a + 1);
    return max (sparse_maximo[a][i], sparse_maximo[b - (1<<i) + 1][i]);
}

int minimizar (int a, int b)
{
    int i = log2(b - a + 1);
    return min (sparse_minimo[a][i], sparse_minimo[b - (1<<i) + 1][i]);
}

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)
{
    if (N <= 3000 && (int)X.size() <= 6000 && (int)S.size() <= 3000)
    {
        int Q = S.size();
        int M = X.size();
        REP(i, 0, M)
        {
            graph[X[i]].pb (Y[i]);
            graph[Y[i]].pb (X[i]);
        }
        vector<int> ans(Q, 0);
        REP(i, 0, Q)
        {
            if (S[i] < L[i] || E[i] > R[i])
            {
                ans[i] = 0;
                continue;
            }
            possiveis[0].push (S[i]);
            dfs (S[i], i, 0, R[i], L[i]);
            while (!possiveis[0].empty())
            {
                dfs (possiveis[0].front(), i, 1, R[i], L[i]);
                if (possiveis[0].front() <= R[i] && possiveis[0].front() >= L[i])
                    possiveis[1].push (possiveis[0].front());
                possiveis[0].pop();
                if (visited[E[i]] > i)
                {
                    ans[i] = 1;
                    while (!possiveis[0].empty())
                        possiveis[0].pop();
                    while (!possiveis[1].empty())
                        possiveis[1].pop();
                    break;
                }
            }
            if (ans[i] != 0)
                continue;
            while (!possiveis[1].empty())
            {
                dfs (possiveis[1].front(), i, 2, R[i], L[i]);
                possiveis[1].pop();
                if (visited[E[i]] > i)
                {
                    ans[i] = 1;
                    while (!possiveis[1].empty())
                        possiveis[1].pop();
                    break;
                }
            }
        }
        return ans;
    }
    int Q = S.size();
    vector<int> ans(Q);
    REP(i, 0, (int)X.size())
    {
        graph[X[i]].pb (Y[i]);
        graph[Y[i]].pb (X[i]);
    }
    REP(i, 0, N)
    {
        if ((int)graph[i].size() == 1)
        {
            ordem[0] = i;
            posicao[i] = 0;
            break;
        }
    }
    ordem[1] = graph[ordem[0]][0];
    posicao[ordem[1]] = 1;
    REP(i, 2, N)
    {
        if (graph[ordem[i-1]][0] == ordem[i-2])
            ordem[i] = graph[ordem[i-1]][1];
        else
            ordem[i] = graph[ordem[i-1]][0];
        posicao[ordem[i]] = i;
    }
    create(N);
    REP(i, 0, Q)
    {
        int inicio = posicao[S[i]];
        int fim = posicao[E[i]];
        if (S[i] < L[i] || E[i] > R[i])
        {
            ans[i] = 0;
            continue;
        }
        if (inicio < fim)
        {
            int minimo = inicio, maximo = fim;
            while (minimo != maximo)
            {
                int med = (minimo + maximo + 1)/2;
                if (minimizar(inicio, med) < L[i])
                    maximo = med - 1;
                else
                    minimo = med;
            }
            if (maximizar(minimo, fim) > R[i])
                ans[i] = 0;
            else
                ans[i] = 1;
        }
        else
        {
            int minimo = fim, maximo = inicio;
            while (minimo != maximo)
            {
                int med = (minimo + maximo)/2;
                if (minimizar(med, inicio) < L[i])
                    minimo = med + 1;
                else
                    maximo = med;
            }
            if (maximizar(fim, minimo) > R[i])
                ans[i] = 0;
            else
                ans[i] = 1;
        }
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4916 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 4 ms 5020 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4916 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 4 ms 5020 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 275 ms 5328 KB Output is correct
11 Correct 159 ms 5276 KB Output is correct
12 Correct 19 ms 5452 KB Output is correct
13 Correct 260 ms 5344 KB Output is correct
14 Correct 186 ms 5280 KB Output is correct
15 Correct 270 ms 5444 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 784 ms 54224 KB Output is correct
2 Correct 726 ms 54340 KB Output is correct
3 Correct 748 ms 54340 KB Output is correct
4 Correct 683 ms 54348 KB Output is correct
5 Correct 651 ms 54344 KB Output is correct
6 Correct 715 ms 54340 KB Output is correct
7 Correct 668 ms 54268 KB Output is correct
8 Correct 651 ms 54348 KB Output is correct
9 Correct 388 ms 54256 KB Output is correct
10 Correct 378 ms 54480 KB Output is correct
11 Correct 393 ms 54300 KB Output is correct
12 Correct 425 ms 54268 KB Output is correct
13 Correct 679 ms 54344 KB Output is correct
14 Correct 726 ms 54344 KB Output is correct
15 Correct 702 ms 54348 KB Output is correct
16 Correct 699 ms 54380 KB Output is correct
17 Correct 669 ms 54340 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4916 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 4 ms 5020 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 275 ms 5328 KB Output is correct
11 Correct 159 ms 5276 KB Output is correct
12 Correct 19 ms 5452 KB Output is correct
13 Correct 260 ms 5344 KB Output is correct
14 Correct 186 ms 5280 KB Output is correct
15 Correct 270 ms 5444 KB Output is correct
16 Correct 784 ms 54224 KB Output is correct
17 Correct 726 ms 54340 KB Output is correct
18 Correct 748 ms 54340 KB Output is correct
19 Correct 683 ms 54348 KB Output is correct
20 Correct 651 ms 54344 KB Output is correct
21 Correct 715 ms 54340 KB Output is correct
22 Correct 668 ms 54268 KB Output is correct
23 Correct 651 ms 54348 KB Output is correct
24 Correct 388 ms 54256 KB Output is correct
25 Correct 378 ms 54480 KB Output is correct
26 Correct 393 ms 54300 KB Output is correct
27 Correct 425 ms 54268 KB Output is correct
28 Correct 679 ms 54344 KB Output is correct
29 Correct 726 ms 54344 KB Output is correct
30 Correct 702 ms 54348 KB Output is correct
31 Correct 699 ms 54380 KB Output is correct
32 Correct 669 ms 54340 KB Output is correct
33 Incorrect 283 ms 62140 KB Output isn't correct
34 Halted 0 ms 0 KB -