Submission #205097

#	Time	Username	Problem	Language	Result	Execution time	Memory
205097		medk	Werewolf (IOI18_werewolf)	C++14	15 / 100	4101 ms	40192 KiB

werewolf

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

#define ll long long
#define pb push_back
#define x first
#define y second

using namespace std;

vector<vector<int>> g(200001);
unordered_set<int> st;
vector<bool> vis(200001);

void dfs1(int u, int l)
{
    st.insert(u);
    for(int v:g[u])
    {
        if(v<l || st.count(v)) continue;
        dfs1(v,l);
    }
}

int dfs2(int u, int r)
{
    int ret=st.count(u);
    vis[u]=1;
    for(int v:g[u])
    {
        if(v>r || vis[v]) continue;
        ret|=dfs2(v,r);
    }
    return ret;
}

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 m=x.size(), q=s.size();
    for(int i=0;i<m;i++) g[x[i]].pb(y[i]), g[y[i]].pb(x[i]);
    vector<int> ans;
    for(int i=0;i<q;i++)
    {
        st.clear();
        dfs1(s[i],l[i]);
        for(int j=0;j<n;j++) vis[j]=0;
        ans.pb(dfs2(e[i],r[i]));
    }
    return ans;
}

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