Submission #991114

#	Time	Username	Problem	Language	Result	Execution time	Memory
991114		fv3	Werewolf (IOI18_werewolf)	C++14	0 / 100	4043 ms	26644 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;
typedef long long ll;

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
    // Construct adjacency list
    vector<vector<int>> adj(X.size());
    for (int i = 0; i < X.size(); i++)
    {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    vector<int> validity(S.size());
    for (int q = 0; q < S.size(); q++)
    {
        vector<int> visited(N);

        queue<int> hq; // Human queue
        queue<int> wq; // Werewolf queue

        // BFS as human
        hq.push(S[q]);
        visited[S[q]] = 1;
        while (!hq.empty())
        {
            int s = hq.front();
            hq.pop();

            if (s == E[q])
            {
                validity[q] = 1;
                break;
            }

            for (auto node : adj[s])
            {
                if (visited[node]) continue;
                if (node >= L[q])
                {
                    visited[node] = 1;
                    hq.push(node);
                }
                else if (s <= R[q])
                {
                    visited[node] = 1;
                    wq.push(node);
                }
            }
        }

        if (validity[q]) continue;

        // BFS as werewolf
        while (!wq.empty())
        {
            int s = wq.front();
            wq.pop();

            if (s == E[q])
            {
                validity[q] = 1;
                break;
            }

            for (auto node : adj[s])
            {
                if (visited[node] || node > R[q]) continue;
                visited[node] = 1;
                wq.push(node);
            }
        }
    }

    return validity;
}

// X and Y --> describe the graph
// S and E --> start and ending point
// L and R --> As human you cannot be in c_i for 0 <= i <= L
//             As werewolf you cannot be in c_i for R <= i <= N - 1
//
// Subtask 1: N = 100, M = 200, Q = 100
// BFS to all cities less than R and push all neighbours greater than to another queue
// BFS from the other queue untill you find the desired city
// O((N+M)*Q) = O(2000000) ez
//
// Subtask 3: All cities are on a line
// 

// c_0 is sure to be unsafe for humans
// c_N-1 is sure to be unsafe for werewolfs

/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

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:11:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (int i = 0; i < X.size(); i++)
      |                     ~~^~~~~~~~~~
werewolf.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int q = 0; q < S.size(); q++)
      |                     ~~^~~~~~~~~~

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