Submission #425640

#	Time	Username	Problem	Language	Result	Execution time	Memory
425640		TryMax	Werewolf (IOI18_werewolf)	C++17	15 / 100	4102 ms	31580 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#ifdef LOCAL
    #include "grader.cpp"
#endif // LOCAL

#define pb push_back

using namespace std;

const int N = 2e5 + 10;

int canh[N], canw[N];
vector<int> a[N];

void dfs_l(int u, int num){
    canw[u] = 1;
    for(auto v : a[u])
        if(canw[v] == 0 && v <= num)
            dfs_l(v, num);
}

void dfs_g(int u, int num){
    canh[u] = 1;
    for(auto v : a[u])
        if(canh[v] == 0 && v >= num)
            dfs_g(v, num);
}

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 q = s.size();
    int m = x.size();
    vector<int> ans;
    ans.resize(q);
    for(int i = 0; i < m; ++i){
        a[x[i]].pb(y[i]);
        a[y[i]].pb(x[i]);
    }
    for(int i = 0; i < q; ++i){
        for(int j = 0; j < n; ++j)
            canh[j] = canw[j] = 0;
        dfs_g(s[i], l[i]);
        dfs_l(e[i], r[i]);
        bool f = false;
        for(int j = l[i]; j <= r[i]; ++j)
            f |= (canh[j] && canw[j]);
        ans[i] = f;
    }
    return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

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