제출 #972393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
972393		vladilius	늑대인간 (IOI18_werewolf)	C++17	0 / 100	1095 ms	86556 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r){
    vector<int> g[n + 1];
    int m = (int) x.size();
    if (m != (n - 1)) exit(0);
    for (int i = 0; i < m; i++){
        x[i]++; y[i]++;
        g[x[i]].pb(y[i]);
        g[y[i]].pb(x[i]);
    }
    for (int i = 0; i < n; i++){
        l[i]++; r[i]++;
        s[i]++; e[i]++;
    }
    int f = 0;
    for (int i = 1; i <= n; i++){
        if (g[i].size() == 1){
            f = i;
            break;
        }
    }
    vector<int> a = {0};
    function<void(int, int)> dfs = [&](int v, int pr){
        a.pb(v);
        for (int i: g[v]){
            if (i != pr){
                dfs(i, v);
            }
        }
    };
    dfs(f, 0);
    
    const int lg = ceil(log2(n));
    vector<vector<int>> sp1(n + 1, vector<int>(lg + 1));
    vector<vector<int>> sp2 = sp1;
    for (int i = 1; i <= n; i++){
        sp1[i][0] = a[i];
        sp2[i][0] = a[i];
    }
    for (int k = 1; k <= lg; k++){
        for (int i = 1; i + (1 << k) <= n + 1; i++){
            sp1[i][k] = min(sp1[i][k - 1], sp1[i + (1 << (k - 1))][k - 1]);
            sp2[i][k] = max(sp2[i][k - 1], sp2[i + (1 << (k - 1))][k - 1]);
        }
    }
    vector<int> log(n + 1);
    for (int i = 2; i <= n; i++){
        log[i] = log[i / 2] + 1;
    }
    
    auto get_min = [&](int l, int r){
        int k = log[r - l + 1];
        return min(sp1[l][k], sp1[r - (1 << k) + 1][k]);
    };
    
    auto get_max = [&](int l, int r){
        int k = log[r - l + 1];
        return max(sp2[l][k], sp2[r - (1 << k) + 1][k]);
    };
    
    auto check = [&](int x, pii& R){
        return (R.ff <= x && x <= R.ss);
    };
    
    auto find = [&](int x, pii R){
        int l1 = x, r1 = n;
        while (l1 + 1 < r1){
            int m = (l1 + r1) / 2;
            if (!check(get_min(x, m), R) || !check(get_max(x, m), R)){
                r1 = m - 1;
            }
            else {
                l1 = m;
            }
        }
        if (x <= r1 && check(get_min(x, r1), R) && check(get_max(x, r1), R)){
            l1 = r1;
        }
        
        int l2 = 1, r2 = x;
        while (l2 + 1 < r2){
            int m = (l2 + r2) / 2;
            if (!check(get_min(m, x), R) || !check(get_max(m, x), R)){
                l2 = m + 1;
            }
            else {
                r2 = m;
            }
        }
        if (l2 <= x && check(get_min(l2, x), R) && check(get_max(l2, x), R)){
            r2 = l2;
        }
        return make_pair(r2, l1);
    };
    
    auto inter = [&](pii A, pii B){
        if (A.ff > B.ff) swap(A, B);
        return (A.ss >= B.ff);
    };
    
    int q = (int) s.size();
    vector<int> out;
    for (int i = 0; i < q; i++){
        int u = s[i], v = e[i];
        pii A = find(u, {l[i], n});
        pii B = find(v, {1, r[i]});
        out.pb(inter(A, B));
    }
    return out;
}

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