제출 #767870

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
767870		Alihan_8	늑대인간 (IOI18_werewolf)	C++17	15 / 100	4038 ms	30736 KiB

werewolf

#include <bits/stdc++.h>

//#include "werewolf.h"

#define Read_Input true

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
//#define int long long

template <class _T>
bool chmin(_T &x, const _T &y){
    bool flag = false;
    if ( x > y ){
        x = y; flag |= true;
    }
    return flag;
}

template <class _T>
bool chmax(_T &x, const _T &y){
    bool flag = false;
    if ( x < y ){
        x = y; flag |= true;
    }
    return flag;
}

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 = (int)X.size(), q = (int)S.size();
    vector <int> g[n];
    for ( int i = 0; i < m; i++ ){
        g[X[i]].pb(Y[i]);
        g[Y[i]].pb(X[i]);
    }
    vector <int> ans(q);
    auto bfs = [&](int st, int en, int L, int R){
        if ( st < L or en > R ){
            return false;
        }
        vector <array<int,2>> dp(n, {false, false});
        queue <int> q; q.push(st);
        dp[st][0] = true;
        while ( !q.empty() ){
            auto x = q.front();
            q.pop();
            for ( auto to: g[x] ){
                if ( to >= L and !dp[to][0] ){
                    dp[to][0] = true;
                    q.push(to);
                }
            }
        }
        q.push(en); dp[en][1] = true;
        while ( !q.empty() ){
            auto x = q.front();
            q.pop();
            for ( auto to: g[x] ){
                if ( to <= R and !dp[to][1] ){
                    dp[to][1] = true;
                    q.push(to);
                }
            }
        }
        for ( int i = 0; i < n; i++ ){
            if ( dp[i][0] & dp[i][1] ){
                return true;
            }
        }
        return false;
    };
    for ( int i = 0; i < q; i++ ){
        ans[i] = bfs(S[i], E[i], L[i], R[i]);
    }
    return ans;
}

#ifndef EVAL
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q; cin >> n >> m >> q;
    vector <int> x(m), y(m);
    for ( auto &i: x ) cin >> i;
    for ( auto &i: y ) cin >> i;
    vector <int> s(q), e(q), l(q), r(q);
    for ( auto &i: s ) cin >> i;
    for ( auto &i: e ) cin >> i;
    for ( auto &i: l ) cin >> i;
    for ( auto &i: r ) cin >> i;
    for ( auto i: check_validity(n, x, y, s, e, l, r) ){
        cout << i << ' ';
    }

    cout << '\n';
}
/*
6 6 3
5 1 1 3 3 5
1 2 3 4 0 2
4 4 5
2 2 4
1 2 3
2 2 4

answer : {1, 0 ,0}
*/
#endif // EVAL

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