Submission #434170

#	Time	Username	Problem	Language	Result	Execution time	Memory
434170		Tiago_Marques	Werewolf (IOI18_werewolf)	C++17	15 / 100	4046 ms	40516 KiB

werewolf

#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

vector<int> graph[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);
        }
    }
}

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

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