oj.uz

Submission #434170

# Submission time Handle Problem Language Result Execution time Memory
434170 2021-06-20T16:40:18 Z Tiago_Marques Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 40516 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]);
            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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 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 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 255 ms 5316 KB Output is correct
11 Correct 159 ms 5264 KB Output is correct
12 Correct 18 ms 5536 KB Output is correct
13 Correct 253 ms 5332 KB Output is correct
14 Correct 229 ms 5248 KB Output is correct
15 Correct 276 ms 5444 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 255 ms 5316 KB Output is correct
11 Correct 159 ms 5264 KB Output is correct
12 Correct 18 ms 5536 KB Output is correct
13 Correct 253 ms 5332 KB Output is correct
14 Correct 229 ms 5248 KB Output is correct
15 Correct 276 ms 5444 KB Output is correct
16 Execution timed out 4046 ms 40516 KB Time limit exceeded
17 Halted 0 ms 0 KB -