Submission #676137

#	Time	Username	Problem	Language	Result	Execution time	Memory
676137		coding_snorlax	늑대인간 (IOI18_werewolf)	C++14	15 / 100	899 ms	41856 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
vector<int> G[200002];
int vis1[3002]={0};
int vis2[3002]={0};
void dfs_L(int node,int Left_bound){
    vis1[node]=1;
    for(int i:G[node]) {if(!vis1[i] && i>=Left_bound) dfs_L(i,Left_bound);};
}
void dfs_R(int node,int Right_bound){
    vis2[node]=1;
    for(int i:G[node]) {if(!vis2[i] && i<=Right_bound) dfs_R(i,Right_bound);};
}
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R){
    vector<int> answer;
    for(int i=0;i<(int)X.size();i++){G[X[i]].push_back(Y[i]);G[Y[i]].push_back(X[i]);}
    for(int i=0;i<(int)S.size();i++){
        for(int j=0;j<N;j++) vis1[j]=0;
        dfs_L(S[i],L[i]);
        for(int j=0;j<N;j++) vis2[j]=0;
        dfs_R(E[i],R[i]);
        int flag=0;
        for(int i=0;i<N;i++){
            if(vis1[i]&&vis2[i]) flag=1;
        }
        if(flag) answer.push_back(1);
        else answer.push_back(0);
    }
    return answer;
}

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