oj.uz

답안 #819270

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
819270 2023-08-10T08:45:56 Z vjudge1 늑대인간 (IOI18_werewolf) C++17
15 / 100
 1170 ms 67144 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(l > r || 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;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 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 3 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

# 결과 실행 시간 메모리 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 3 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 198 ms 5288 KB Output is correct
11 Correct 103 ms 5240 KB Output is correct
12 Correct 20 ms 5332 KB Output is correct
13 Correct 237 ms 5280 KB Output is correct
14 Correct 142 ms 5244 KB Output is correct
15 Correct 181 ms 5400 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1170 ms 58640 KB Output is correct
2 Correct 477 ms 67048 KB Output is correct
3 Incorrect 422 ms 67144 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 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 3 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 198 ms 5288 KB Output is correct
11 Correct 103 ms 5240 KB Output is correct
12 Correct 20 ms 5332 KB Output is correct
13 Correct 237 ms 5280 KB Output is correct
14 Correct 142 ms 5244 KB Output is correct
15 Correct 181 ms 5400 KB Output is correct
16 Correct 1170 ms 58640 KB Output is correct
17 Correct 477 ms 67048 KB Output is correct
18 Incorrect 422 ms 67144 KB Output isn't correct
19 Halted 0 ms 0 KB -