oj.uz

Submission #767903

# Submission time Handle Problem Language Result Execution time Memory
767903 2023-06-27T09:17:30 Z Alihan_8 Werewolf (IOI18_werewolf) C++17
0 / 100
 4000 ms 63276 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]);
    }
    int root = -1;
    for ( int i = 0; i < n; i++ ){
        if ( (int)g[i].size() == 1 ){
            root = i;
        }
    }
    vector <int> ord, pos(n, -1);
    ord.pb(root);
    while ( (int)ord.size() < n ){
        int sz = (int)ord.size();
        for ( auto to: g[ord.back()] ){
            if ( sz == 1 or to != ord[sz - 2] ){
                ord.pb(to); break;
            }
        }
    }
    const int inf = 1e9 + 1;
    struct Sp{
        vector <vector<int>> T;
        Sp(vector <int> def){
            int n = (int)def.size();
            T.resize(21); T[0].resize(n);
            for ( int i = 0; i < n; i++ ){
                T[0][i] = def[i];
            }
            for ( int i = 1; i < 21; i++ ){
                int k = 1 << i - 1;
                T[i].resize(n);
                for ( int j = 0; j < n; j++ ){
                    T[i][j] = min(T[i - 1][j], T[i - 1][min(j + k, n - 1)]);
                }
            }
        }
        int get(int l, int r){
            int lg = __lg(r - l + 1), k = 1 << lg;
            return min(T[lg][l], T[lg][r - k + 1]);
        }
    };
    for ( int i = 0; i < n; i++ ){
        pos[ord[i]] = i;
    }
    Sp Mn(ord);
    for ( auto &i: ord ) i *= -1;
    Sp Mx(ord);
    auto query = [&](int l, int r, int L, int R){
        l = pos[l], r = pos[r];
        if ( l > r ){
            swap(l, r);
            if ( -ord[l] > R or -ord[r] < L ){
                return false;
            }
            int tl = l, tr = r + 1, x = -1, y = n;
            while ( tl + 1 < tr ){
                int md = (tl + tr) >> 1;
                if ( -Mx.get(tl, md) > R ){
                    tr = md;
                }
                else tl = md;
            } x = tl;
            tl = l - 1, tr = r;
            while ( tl + 1 < tr ){
                int md = (tl + tr) >> 1;
                if ( Mn.get(md, tr) < L ){
                    tl = md;
                } else tr = md;
            } y = tr;
            return x >= y;
        }
        if ( -ord[l] < L or -ord[r] > R ){
            return false;
        }
        int tl = l, tr = r + 1, x = -1, y = n;
        while ( tl + 1 < tr ){
            int md = (tl + tr) >> 1;
            if ( Mn.get(tl, md) < L ){
                tr = md;
            }
            else tl = md + 1;
        } x = tl;
        tl = l - 1, tr = r;
        while ( tl + 1 < tr ){
            int md = (tl + tr) >> 1;
            if ( -Mx.get(md, tr) > R ){
                tl = md;
            } else tr = md;
        } y = tr;
        return x >= y;
    };
    vector <int> ans(q);
    for ( int i = 0; i < q; i++ ){
        ans[i] = query(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

Compilation message

werewolf.cpp: In constructor 'check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)::Sp::Sp(std::vector<int>)':
werewolf.cpp:65:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   65 |                 int k = 1 << i - 1;
      |                              ~~^~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:55:15: warning: unused variable 'inf' [-Wunused-variable]
   55 |     const int inf = 1e9 + 1;
      |               ^~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 57164 KB Output is correct
2 Correct 378 ms 63132 KB Output is correct
3 Correct 371 ms 63020 KB Output is correct
4 Incorrect 382 ms 63276 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

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