Submission #115072

#	Time	Username	Problem	Language	Result	Execution time	Memory
115072		zoooma13	Werewolf (IOI18_werewolf)	C++14	15 / 100	370 ms	19632 KiB

werewolf

#include "werewolf.h"
//#include "grader.cpp"
#include "bits/stdc++.h"
using namespace std;

#define MAX_N 3003

int n ,m ,q;
vector <int> adj[MAX_N];

bool human(int x ,int l ,int r){
    return l <= x;
}
bool wolf(int x ,int l ,int r){
    return x <= r;
}
bool both(int x ,int l ,int r){
    return l <= x && x <= r;
}

bool vis[2][MAX_N];
bool bfs(int s ,int e ,int l ,int r){
    queue <pair<int ,bool>> nxt; nxt.push({s ,0});
    memset(vis ,0 ,sizeof vis);
    while(!nxt.empty()){
        auto now = nxt.front(); nxt.pop();
        if(vis[now.second][now.first])
            continue;
        vis[now.second][now.first] = 1;

        if(!both(now.first ,l ,r) && !now.second && wolf(now.first ,l ,r))
            continue;
        if(!both(now.first ,l ,r) && now.second && human(now.first ,l ,r))
            continue;
        //cout << now.first << ' ' << now.second << endl;
        if(now.first == e && (now.second || both(now.first , l ,r)))
            return 1;

        for(int v : adj[now.first]){
            if(!now.second && both(now.first ,l ,r))
                nxt.push({v ,0}) ,nxt.push({v ,1});
            else if(!now.second)
                nxt.push({v ,0});
            else
                nxt.push({v ,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)
{
    n = N ,m = X.size() ,q = S.size();
    for(int i=0; i<m; i++)
        adj[X[i]].push_back(Y[i]),
        adj[Y[i]].push_back(X[i]);
    vector <int> A(q);
    for(int i=0; i<q; i++)
        A[i] = bfs(S[i] ,E[i] ,L[i] ,R[i]);
    return A;
}

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