Submission #1015384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015384		nisanduu	늑대인간 (IOI18_werewolf)	C++14	15 / 100	4048 ms	24316 KiB

werewolf

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

// 0 - Wolf
// 1 - Human

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<vector<ll>> adj(N+1);
        ll M = X.size();
        for(ll i=0;i<M;i++){
            adj[X[i]].push_back(Y[i]);
            adj[Y[i]].push_back(X[i]);
        }
        
        ll Q = S.size();
        vector<int> ans(Q);
        for(ll i=0;i<Q;i++){
            vector<int> vis(N+1),vis1(N+1),arr(N+1);

            queue<ll> q,q1;
            q.push(S[i]);
            while(!q.empty()){
                ll node = q.front();
                q.pop();
                if(vis[node]==1) continue;
                arr[node]=1;
                vis[node]=1;
                for(auto el:adj[node]){
                    if(!vis[el]&&el>=L[i]){
                        q.push(el);
                    }
                }
            }
            q1.push(E[i]);
            while(!q1.empty()){
                ll node = q1.front();
                q1.pop();
                if(vis1[node]==1) continue;
                arr[node]+=1;
                vis1[node]=1;
                for(auto el:adj[node]){
                    if(!vis1[el]&&el<=R[i]){
                        q1.push(el);
                    }
                }
            }
            for(ll j=0;j<N;j++){
                if(j>=L[i]&&arr[j]==2&&j<=R[i]){
                    ans[i]=1;
                }
            }
            // for(ll j=S[i]+1;j<=N;j++){
            //     // if(arr[j]==2&&j>=L[i]&&j<=R[i]){
            //     //     ans[i]=1;
            //     // }
            //     cout<<arr[j]<<endl;
            // }
            //break;
        }
        return ans;
}

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