oj.uz

Submission #964649

# Submission time Handle Problem Language Result Execution time Memory
964649 2024-04-17T09:22:02 Z fve5 Werewolf (IOI18_werewolf) C++17
0 / 100
 4000 ms 35152 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;

vector<int> solve_naive(
    int N, int M, int Q,
    vector<int> X, vector<int> Y,
    vector<int> S, vector<int> E,
    vector<int> L, vector<int> R
) {
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    vector<int> ans(Q);
    for (int i = 0; i < Q; i++) {
        vector<array<bool, 2>> visited(N);
        queue<pair<int, bool>> q;

        q.emplace(S[i], 0);
        while (!q.empty()) {
            auto [node, st] = q.front(); q.pop();
            if (visited[node][st]) continue;
            visited[node][st] = true;
            
            for (auto x: adj[node]) {
                if (!st && x >= L[i]) q.emplace(x, st);
                if (st && x <= R[i]) q.emplace(x, st);
            }

            if (L[i] <= node && node <= R[i]) q.emplace(node, !st);
        }

        ans[i] = visited[E[i]][1];
    }

    return ans;
}

vector<int> check_validity(
    int N,
    vector<int> X, vector<int> Y,
    vector<int> S, vector<int> E,
    vector<int> L, vector<int> R
) {
    int M = X.size();
    int Q = S.size();

    if (N <= 3000 && M <= 6000 && Q <= 3000) {
        return solve_naive(N, M, Q, X, Y, S, E, L, R);
    }
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
   54 | }
      | ^

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

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