Submission #792642

#	Time	Username	Problem	Language	Result	Execution time	Memory
792642		fatemetmhr	Werewolf (IOI18_werewolf)	C++17	15 / 100	210 ms	19992 KiB

werewolf

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

using namespace std;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
#define mp     make_pair

typedef long long ll;

const int maxn5 = 3e3 + 10;
const int lg    = 20;

vector <int> adj[maxn5], ret;
bool mark[maxn5], mark2[maxn5];
int liml, limr, n;

void dfs(int v){
    mark[v] = true;
    for(auto u : adj[v]) if(u >= liml && u <= limr && !mark[u])
        dfs(u);
}

std::vector<int> check_validity(int N, std::vector<int> x, std::vector<int> y,
                                std::vector<int> s, std::vector<int> e,
                                std::vector<int> l, std::vector<int> r) {
    n = N;
    int q = s.size();
    int m = x.size();
    for(int i = 0; i < m; i++){
        adj[x[i]].pb(y[i]);
        adj[y[i]].pb(x[i]);
    }
    for(int i = 0; i < q; i++){
        liml = 0, limr = r[i];
        memset(mark, false, sizeof mark);
        dfs(e[i]);
        for(int j = 0; j < n; j++)
            mark2[j] = mark[j];
        memset(mark, false, sizeof mark);
        liml = l[i]; limr = n;
        dfs(s[i]);
        bool re = false;
        for(int j = 0; j < n; j++)
            re |= (mark[j] && mark2[j]);
        ret.pb(re);
    }
    return ret;
}

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