oj.uz

Submission #1016347

# Submission time Handle Problem Language Result Execution time Memory
1016347 2024-07-07T20:56:40 Z lacito Werewolf (IOI18_werewolf) C++14
15 / 100
 177 ms 19544 KB 
#include "werewolf.h"
using namespace std;

const int MAXN = 3000;

vector<int> g[MAXN];
vector<bool> vis1;
vector <bool> vis2;
int n, l, r;

void dfs1(int v, bool human) {
    vis1[v] = true;
    for (int u : g[v]) {
        if (!vis1[u]) {
            if (human && u >= l || !human && u <= r) { // werewolf condition
                dfs1(u, human);
            }
        }
    }
}

void dfs2(int v, bool human) {
    vis2[v] = true;
    for (int u : g[v]) {
        if (!vis2[u]) {
            if (human && u >= l || !human && u <= r) { // werewolf condition
                dfs2(u, human);
            }
        }
    }
}

int solve(int s, int e) {
    vis1.assign(n, false);
    vis2.assign(n, false);
    dfs1(s, true);
    dfs2(e, false);
    for (int i = 0; i < vis1.size(); ++i){
        if (vis1[i] && vis2[i]) return 1;
    }
    return 0;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    for (int i = 0; i < X.size(); i++) {
        // road between X[i] and Y[i]
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    n = N;
    int Q = S.size();
    vector<int> A(Q);
    for (int i = 0; i < Q; ++i) {
        l = L[i];
        r = R[i];
        A[i] = solve(S[i], E[i]);
    }
    return A;
}

Compilation message

werewolf.cpp: In function 'void dfs1(int, bool)':
werewolf.cpp:15:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   15 |             if (human && u >= l || !human && u <= r) { // werewolf condition
      |                 ~~~~~~^~~~~~~~~
werewolf.cpp: In function 'void dfs2(int, bool)':
werewolf.cpp:26:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   26 |             if (human && u >= l || !human && u <= r) { // werewolf condition
      |                 ~~~~~~^~~~~~~~~
werewolf.cpp: In function 'int solve(int, int)':
werewolf.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 0; i < vis1.size(); ++i){
      |                     ~~^~~~~~~~~~~~~
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:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < X.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 158 ms 604 KB Output is correct
11 Correct 66 ms 600 KB Output is correct
12 Correct 24 ms 856 KB Output is correct
13 Correct 177 ms 752 KB Output is correct
14 Correct 70 ms 604 KB Output is correct
15 Correct 174 ms 868 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 96 ms 19544 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 158 ms 604 KB Output is correct
11 Correct 66 ms 600 KB Output is correct
12 Correct 24 ms 856 KB Output is correct
13 Correct 177 ms 752 KB Output is correct
14 Correct 70 ms 604 KB Output is correct
15 Correct 174 ms 868 KB Output is correct
16 Runtime error 96 ms 19544 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -