Submission #295808

#	Time	Username	Problem	Language	Result	Execution time	Memory
295808		daniel920712	늑대인간 (IOI18_werewolf)	C++14	15 / 100	4075 ms	21880 KiB

werewolf

#include "werewolf.h"
#include <queue>
#include <vector>
using namespace std;
queue < pair < int , int > > all;
vector < int > Next[200005];
bool have[5][200005];
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(),M=X.size(),i,j,ok,a,b;
    vector<int> A(Q);
    for(i=0;i<M;i++)
    {
        Next[X[i]].push_back(Y[i]);
        Next[Y[i]].push_back(X[i]);
    }
    for (i=0;i<Q;i++)
    {
        for(j=0;j<N;j++) have[0][j]=have[1][j]=0;
        ok=0;
        all.push(make_pair(S[i],0));
        while(!all.empty())
        {
            a=all.front().first;
            b=all.front().second;
            all.pop();
            if(a==E[i]&&b==1)
            {
                ok=1;
                break;
            }
            if(have[b][a]) continue;
            if(b==0&&a<L[i]) continue;
            if(b==1&&a>R[i]) continue;
            have[b][a]=1;
            if(b==0&&a>=L[i]&&a<=R[i]) all.push(make_pair(a,1));

            for(auto i:Next[a]) all.push(make_pair(i,b));
        }
        while(!all.empty()) all.pop();
        A[i]=ok;

    }

    return A;
}

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