Submission #1016347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016347		lacito	Werewolf (IOI18_werewolf)	C++14	15 / 100	177 ms	19544 KiB

werewolf

#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 (stderr)

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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51