oj.uz

Submission #434168

# Submission time Handle Problem Language Result Execution time Memory
434168 2021-06-20T16:37:45 Z Tiago_Marques Werewolf (IOI18_werewolf) C++17
0 / 100
 4000 ms 39756 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

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]);
            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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4075 ms 39756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -