Submission #828491

#	Time	Username	Problem	Language	Result	Execution time	Memory
828491		vnm06	Werewolf (IOI18_werewolf)	C++14	15 / 100	262 ms	27972 KiB

werewolf

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

using namespace std;

int n, m;
int be, en, le, ri;
vector<int> res;
vector<int> gr[3005];
bool used[3005][2];

void dfs(int v, int ty)
{
    used[v][ty]=1;
    if(ty==0 && v<=ri && !used[v][1]) dfs(v, 1);
    int brs=gr[v].size();
    for(int i=0; i<brs; i++)
    {
        int nv=gr[v][i];
        if(ty==0 && nv<le) continue;
        if(ty==1 && nv>ri) continue;
        if(used[nv][ty]) continue;
        dfs(nv, ty);
    }
}

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)
{
    n=N;
    m=X.size();
    for(int i=0; i<m; i++)
    {
        gr[X[i]].push_back(Y[i]);
        gr[Y[i]].push_back(X[i]);
    }
    int q=S.size();
    for(int i=0; i<q; i++)
    {
        be=S[i], en=E[i], le=L[i], ri=R[i];
        if(be<le || en>ri) {res.push_back(0); continue;}
        memset(used, 0, sizeof(used));
        dfs(be, 0);
        res.push_back(used[en][1]);
    }
    return res;
}

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