oj.uz

Submission #972428

# Submission time Handle Problem Language Result Execution time Memory
972428 2024-04-30T12:02:39 Z vladilius Werewolf (IOI18_werewolf) C++17
34 / 100
 1140 ms 95956 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 961 ms 87316 KB Output is correct
2 Correct 1046 ms 95680 KB Output is correct
3 Correct 1004 ms 95520 KB Output is correct
4 Correct 961 ms 95716 KB Output is correct
5 Correct 1014 ms 95876 KB Output is correct
6 Correct 938 ms 95704 KB Output is correct
7 Correct 973 ms 95640 KB Output is correct
8 Correct 819 ms 95808 KB Output is correct
9 Correct 373 ms 95692 KB Output is correct
10 Correct 445 ms 95604 KB Output is correct
11 Correct 541 ms 95696 KB Output is correct
12 Correct 360 ms 95688 KB Output is correct
13 Correct 1081 ms 95948 KB Output is correct
14 Correct 1123 ms 95956 KB Output is correct
15 Correct 1140 ms 95840 KB Output is correct
16 Correct 1105 ms 95580 KB Output is correct
17 Correct 991 ms 95792 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -