Submission #972428

#	Time	Username	Problem	Language	Result	Execution time	Memory
972428		vladilius	늑대인간 (IOI18_werewolf)	C++17	34 / 100	1140 ms	95956 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);
    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++){
        p[a[i]] = i;
    }
    
    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 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 = p[s[i]], v = p[e[i]];
        pii A, B;
        
        int l1 = u, r1 = n;
        while (l1 + 1 < r1){
            int m = (l1 + r1) / 2;
            int k = get_min(u, m);
            if (k < l[i]){
                r1 = m - 1;
            }
            else {
                l1 = m;
            }
        }
        if (get_min(u, r1) >= l[i]) l1 = r1;
        
        int l2 = 1, r2 = u;
        while (l2 + 1 < r2){
            int m = (l2 + r2) / 2;
            int k = get_min(m, u);
            if (k < l[i]){
                l2 = m + 1;
            }
            else {
                r2 = m;
            }
        }
        if (get_min(l2, u) >= l[i]) r2 = l2;
        
        A = {r2, l1};
        
        l1 = v; r1 = n;
        while (l1 + 1 < r1){
            int m = (l1 + r1) / 2;
            int k = get_max(v, m);
            if (k > r[i]){
                r1 = m - 1;
            }
            else {
                l1 = m;
            }
        }
        if (get_max(v, r1) <= r[i]) l1 = r1;
        
        l2 = 1; r2 = v;
        while (l2 + 1 < r2){
            int m = (l2 + r2) / 2;
            int k = get_max(m, v);
            if (k > r[i]){
                l2 = m + 1;
            }
            else {
                r2 = m;
            }
        }
        if (get_max(l2, v) <= r[i]) r2 = l2;
        
        B = {r2, l1};
        
        out.pb(inter(A, B));
    }
    return out;
}

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