Submission #294611

#	Time	Username	Problem	Language	Result	Execution time	Memory
294611		Autoratch	Werewolf (IOI18_werewolf)	C++14	15 / 100	4038 ms	35504 KiB

werewolf

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

const int N = 2e5 + 1;

int n,m,q,mn,mx;
vector<int> adj[N];
bool visited[N];
int val[N];

void dfs(int u)
{
    if(visited[u]) return;
    val[u]++;
    visited[u] = true;
    for(int v : adj[u]) if(v>=mn and v<=mx) dfs(v);
}

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 a = x[i],b = y[i];
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector<int> ans;
    for(int i = 0;i < q;i++)
    {
        mn = l[i],mx = n-1;
        for(int j = 0;j < n;j++) visited[j] = false,val[j] = 0;
        dfs(s[i]);
        mn = 0,mx = r[i];
        for(int j = 0;j < n;j++) visited[j] = false;
        dfs(e[i]);
        bool ok = false;
        for(int j = 0;j < n;j++) if(val[j]==2) ok = true;
        ans.push_back(ok);
    }
    return ans;
}

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