Submission #116224

#	Time	Username	Problem	Language	Result	Execution time	Memory
116224		zubec	Werewolf (IOI18_werewolf)	C++14	15 / 100	4091 ms	28216 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 200100;

vector <int> g[N];

int d[2][N];

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();
    std::vector<int> A(Q);

    for (int i = 0; i < X.size(); i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    for (int i = 0; i < Q; i++){
        for (int j = 0; j < N; j++){
            d[0][j] = d[1][j] = 1e9;
        }
        d[0][S[i]] = 0;
        queue <int> q;
        q.push(S[i]);
        while(!q.empty()){
            int v = q.front();
            q.pop();
            for (int j = 0; j < g[v].size(); j++){
                int to = g[v][j];
                if (L[i] <= to && d[0][v] + 1 < d[0][to]){
                    d[0][to] = d[0][v] + 1;
                    q.push(to);
                }
            }
        }
        d[1][E[i]] = 0;
        q.push(E[i]);
        while(!q.empty()){
            int v = q.front();
            q.pop();
            for (int j = 0; j < g[v].size(); j++){
                int to = g[v][j];
                if (to <= R[i] && d[1][v] + 1 < d[1][to]){
                    d[1][to] = d[1][v] + 1;
                    q.push(to);
                }
            }
        }
        bool bb = 0;
        for (int j = L[i]; j <= R[i]; j++){
            if (d[0][j] != 1e9 && d[1][j] != 1e9){
                bb = 1;
                break;
            }
        }
        A[i] = bb;
    }

    return A;
}

Compilation message (stderr)

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:17:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < X.size(); i++){
                     ~~^~~~~~~~~~
werewolf.cpp:31:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < g[v].size(); j++){
                             ~~^~~~~~~~~~~~~
werewolf.cpp:44:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < g[v].size(); j++){
                             ~~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51