Submission #1210275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210275		repsak	Werewolf (IOI18_werewolf)	C++20	0 / 100	4094 ms	22352 KiB

werewolf

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

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 Q = S.size();
    vector<int> A(Q);
    vector<vector<int>> adj(N);
    for(int i = 0; i < X.size(); i++){
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    for(int i = 0; i < Q; i++){
        int low = L[i]; int high = R[i];
        int start = S[i]; int end = E[i];

        queue<vector<int>> q;
        q.push({start, start <= low}); //u, transform state: 0 = human, 1 = can be both, 2 = wolf:     Impossible to go back from 2
        vector<int> visited(N);

        bool isPossible = false;
        while(!q.empty()){
            int u = q.front()[0]; int state = q.front()[1];
            q.pop();

            if(u == end && (state == 2 || state == 1)){
                isPossible = true;
                break;
            }
            
            if(visited[u]) continue;
            visited[u] = 1;

            for(auto v : adj[u]){
                if(v > high){
                    if(state == 2) continue;
                    if(v == end) continue;
                    q.push({v, 0});

                }else if(v < low){
                    if(state == 0) continue;
                    q.push({v, 2});
                }else{
                    q.push({v, 1});
                }
            }
        }

        A[i] = isPossible;
    }

    return A;
}

// 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

// #include "grader.cpp"

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