Submission #1126783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126783		InvMOD	Werewolf (IOI18_werewolf)	C++20	15 / 100	4094 ms	28788 KiB

werewolf

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

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REV(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) "[" #x " = " << (x) << "]"
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 2e5+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;


namespace brute{

    vector<bool> human, werewolf;
    vector<vector<int>> adj;

    void init(int n){
        human.assign(n + 1, false);
        werewolf.assign(n + 1, false);
        adj.assign(n + 1, vector<int>());
    }

    void reinit(int n){
        human.assign(n + 1, false);
        werewolf.assign(n + 1, false);
    }

    void addEdge(int u, int v){
        adj[u].push_back(v);
        adj[v].push_back(u);
        return;
    }

    void Human(int x, int L){
        human[x] = true;
        for(int v : adj[x]){
            if(!human[v]){
                if(v >= L){
                    Human(v, L);
                }
            }
        }
        return;
    }

    void WereWolf(int x, int R){
        werewolf[x] = true;
        for(int v : adj[x]){
            if(!werewolf[v]){
                if(v <= R){
                    WereWolf(v, R);
                }
            }
        }
        return;
    }

    bool good(int x){
        return (werewolf[x] & human[x]) > 0;
    }
}

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 = sz(S), m = sz(X);

    brute::init(N);

    for(int i = 0; i < m; i++){
        brute::addEdge(++X[i], ++Y[i]);
    }

    vector<int> answer;
    for(int i = 0; i < q; i++){
        if(++S[i] >= ++L[i]) brute::Human(S[i], L[i]);
        if(++E[i] <= ++R[i]) brute::WereWolf(E[i], R[i]);

        int good = 0;
        for(int j = 1; j <= N; j++){
            if(brute::good(j)){
                good = 1;
                break;
            }
        }
        answer.push_back(good);

        brute::reinit(N);
    }

    return answer;
}

//#define name "InvMOD"
#ifdef name
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int n,m,q; cin >> n >> m >> q;

    vector<vector<int>> E(2, vector<int>(m));
    FOR(i, 0, 1){
        FOR(j, 0, m - 1){
            cin >> E[i][j];
        }
    }

    vector<vector<int>> Q(4, vector<int>(q));
    FOR(i, 0, 3){
        FOR(j, 0, q - 1){
            cin >> Q[i][j];
        }
    }

    vector<int> answer = check_validity(n, E[0], E[1], Q[0], Q[1], Q[2], Q[3]);

    for(int v : answer) cout << v <<" "; cout <<"\n";
    return 0;
}
#endif // name

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