Submission #816401

#	Time	Username	Problem	Language	Result	Execution time	Memory
816401		ttamx	Werewolf (IOI18_werewolf)	C++14	0 / 100	127 ms	20508 KiB

werewolf

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

using namespace std;

typedef pair<int,int> p2;

const int N=3005;

int n,m,q;
vector<int> adj[N];
int vis[N],vis2[N];

void dfs(int u,int p,int l){
    if(vis[u])return;
    vis[u]=true;
    for(auto v:adj[u]){
        if(v<l)continue;
        dfs(v,u,l);
    }
}

bool dfs2(int u,int p,int r){
    if(vis2[u])return false;
    vis2[u]=true;
    if(vis[u])return true;
    for(auto v:adj[u]){
        if(r<v)continue;
        if(dfs2(v,u,r))return true;
    }
    return false;
}

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++){
		int u=X[i],v=Y[i];
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
    vector<int> ans(q);
	for(int i=0;i<q;i++){
		int s=S[i],e=E[i],l=L[i],r=R[i];
        for(int i=0;i<n;i++)vis[i]=false;
        dfs(s,s,l);
        ans[i]=dfs2(e,e,r);
	}
	return ans;
}

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