oj.uz

Submission #767870

# Submission time Handle Problem Language Result Execution time Memory
767870 2023-06-27T08:45:26 Z Alihan_8 Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 30736 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 187 ms 740 KB Output is correct
11 Correct 101 ms 724 KB Output is correct
12 Correct 17 ms 732 KB Output is correct
13 Correct 206 ms 740 KB Output is correct
14 Correct 125 ms 724 KB Output is correct
15 Correct 170 ms 836 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4038 ms 30736 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 187 ms 740 KB Output is correct
11 Correct 101 ms 724 KB Output is correct
12 Correct 17 ms 732 KB Output is correct
13 Correct 206 ms 740 KB Output is correct
14 Correct 125 ms 724 KB Output is correct
15 Correct 170 ms 836 KB Output is correct
16 Execution timed out 4038 ms 30736 KB Time limit exceeded
17 Halted 0 ms 0 KB -