oj.uz

Submission #819263

# Submission time Handle Problem Language Result Execution time Memory
819263 2023-08-10T08:43:24 Z vjudge1 Werewolf (IOI18_werewolf) C++17
15 / 100
 231 ms 58640 KB 
#include<bits/stdc++.h>
#include "werewolf.h"

using namespace std;

template<typename T>
struct SparseTable {
    int len;
    vector<vector<T>> st;
    T (*F) (T, T);
    void init(vector<T> &a, T (*f) (T, T)) {
        F = f;
        len = (int)a.size();
        int mxpw = 32 - __builtin_clz(len);
        st.resize(mxpw);
        st[0] = a;
        for(int k = 1; k < mxpw; k++) {
            st[k].resize(len - (1 << k));
            for(int i = 0; i < (int)st[k].size(); i++) 
                st[k][i] = F(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
        }
    }
    T get(int l, int r) {
        if(r > l || l < 0 || r >= len) {
            cerr << "Wrong range in Sparse Table\n";
            cerr << "size = " << len << '\n';
            cerr << "range query: " << '[' << l << ", " << r <<  ']' << '\n';
            exit(1);
        }
        int mxpw = 31 - __builtin_clz(r - l + 1);
        return F(st[mxpw][l], st[mxpw][r - (1 << mxpw) + 1]);
    }
};

int n, m, q;
const int N = 2e5 + 10;
vector<int> g[N];

vector<int> cnt;
vector<bool> us;
void dfs(int s, int l, int r) {
    us[s] = 1;
    cnt[s]++;
    for(int to : g[s]) {
        if(us[to] || to > r || to < l) continue;
        dfs(to, l, r);
    }
}

vector<int> order;
int tin[N];

void tour(int s, int p) {
    tin[s] = (int)order.size();
    order.push_back(s);
    for(int to : g[s]) 
        if(to != p) 
            tour(to, s);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                  vector<int> S, vector<int> E,
                                  vector<int> L, vector<int> R) {
    n = N, m = (int)X.size(), q = (int)S.size();
    vector<int> res(q);
    
    for(int i = 0; i < m; i++) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }

    if(n <= 3000 && q <= 3000) {
        for(int i = 0; i < q; i++) {
            cnt.assign(n, 0);
            us.assign(n, false);
            dfs(S[i], L[i], n - 1);
            us.assign(n, false);
            dfs(E[i], 0, R[i]);
            if(*max_element(cnt.begin(), cnt.end()) > 1)
                res[i] = 1;
        }
        return res;
    }
    int root = 0;
    while(root < n && g[root].size() > 1) root++;
    tour(root, root);
    SparseTable<int> mn, mx;
    mn.init(order, [](int a, int b) {return (a > b ? b : a);});
    mx.init(order, [](int a, int b) {return (a < b ? b : a);});
    for(int i = 0; i < q; i++) {
        int x = tin[S[i]], y = tin[E[i]], lb, rb;
        int sl = x, sr = x, el = y, er = y;
        lb = x, rb = n;
        while(rb - lb > 1) {
            int mid = (lb + rb) / 2;
            if(mn.get(x, mid) >= L[i]) lb = mid;
            else rb = mid;
        }
        sr = lb;
        
        lb = 0, rb = x;
        while(rb - lb > 1) {
            int mid = (lb + rb) / 2;
            if(mn.get(mid, x) >= L[i]) rb = mid;
            else lb = mid;
        }
        sl = rb;
        
        lb = y, rb = n;
        while(rb - lb > 1) {
            int mid = (lb + rb) / 2;
            if(mx.get(y, mid) <= R[i]) lb = mid;
            else rb = mid;
        }
        er = lb;
        
        lb = 0, rb = y;
        while(rb - lb > 1) {
            int mid = (lb + rb) / 2;
            if(mx.get(mid, y) <= R[i]) rb = mid;
            else lb = mid;
        }
        el = rb;
        int ll = max(sl, el), rr = min(sr, er);
        res[i] = (ll <= rr);
    }
    return res;
}

Compilation message

werewolf.cpp: In instantiation of 'void SparseTable<T>::init(std::vector<_Tp>&, T (*)(T, T)) [with T = int]':
werewolf.cpp:88:62:   required from here
werewolf.cpp:20:66: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   20 |                 st[k][i] = F(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
      |                                                                ~~^~~

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 231 ms 5204 KB Output is correct
11 Correct 102 ms 5256 KB Output is correct
12 Correct 21 ms 5328 KB Output is correct
13 Correct 231 ms 5272 KB Output is correct
14 Correct 160 ms 5240 KB Output is correct
15 Correct 185 ms 5396 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 163 ms 58640 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 231 ms 5204 KB Output is correct
11 Correct 102 ms 5256 KB Output is correct
12 Correct 21 ms 5328 KB Output is correct
13 Correct 231 ms 5272 KB Output is correct
14 Correct 160 ms 5240 KB Output is correct
15 Correct 185 ms 5396 KB Output is correct
16 Runtime error 163 ms 58640 KB Execution failed because the return code was nonzero
17 Halted 0 ms 0 KB -