oj.uz

Submission #1043479

# Submission time Handle Problem Language Result Execution time Memory
1043479 2024-08-04T09:57:36 Z Zicrus Werewolf (IOI18_werewolf) C++17
34 / 100
 230 ms 44816 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;

typedef long long ll;

ll n, m, q, pow2;
vector<vector<ll>> adj;
vector<ll> a, revA, segMin, segMax;

ll sMin(ll low, ll high) {
    low += pow2; high += pow2;
    ll res = n;
    while (low <= high) {
        if (low & 1) res = min(res, segMin[low++]);
        if (!(high & 1)) res = min(res, segMin[high--]);
        low /= 2; high /= 2;
    }
    return res;
}

ll sMax(ll low, ll high) {
    low += pow2; high += pow2;
    ll res = -1;
    while (low <= high) {
        if (low & 1) res = max(res, segMax[low++]);
        if (!(high & 1)) res = max(res, segMax[high--]);
        low /= 2; high /= 2;
    }
    return res;
}

bool solve(ll s, ll e, ll l, ll r) {
    ll mid = pow2+s;
    while (mid > 1 && segMin[mid] >= l) {
        if ((mid & (mid+1)) == 0) break;
        if (mid & 1) mid++;
        mid /= 2;
    }
    while (mid < pow2) {
        if (segMin[2*mid] < l) mid = 2*mid;
        else mid = 2*mid+1;
    }
    mid = min(mid-pow2, e);
    if (a[mid] < l) mid--;
    return sMax(mid, e) <= r;
}

bool solveRev(ll s, ll e, ll l, ll r) {
    ll mid = pow2+e;
    while (mid > 1 && segMax[mid] <= r) {
        if ((mid & (mid+1)) == 0) break;
        if (mid & 1) mid++;
        mid /= 2;
    }
    while (mid < pow2) {
        if (segMax[2*mid] > r) mid = 2*mid;
        else mid = 2*mid+1;
    }
    mid = min(mid-pow2, s);
    if (a[mid] > r) mid--;
    return sMin(mid, s) >= l;
}

vector<int> check_validity(int n1, vector<int> x, vector<int> y,
                                  vector<int> S, vector<int> E,
                                  vector<int> L, vector<int> R) {
    n = n1; m = x.size(); q = S.size();
    adj = vector<vector<ll>>(n);
    unordered_set<ll> deg1;
    for (int i = 0; i < m; i++) {
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
        if (!deg1.count(x[i])) deg1.insert(x[i]);
        else deg1.erase(x[i]);
        if (!deg1.count(y[i])) deg1.insert(y[i]);
        else deg1.erase(y[i]);
    }
    a = vector<ll>(n);
    revA = vector<ll>(n);
    pow2 = 1ll << (ll)ceil(log2(n));
    segMin = vector<ll>(2*pow2);
    segMax = vector<ll>(2*pow2);
    ll cur = *deg1.begin();
    vector<bool> vst(n);
    for (int i = 0; i < n; i++) {
        vst[cur] = true;
        //
        a[i] = segMin[pow2+i] = segMax[pow2+i] = cur;
        revA[cur] = i;
        //
        for (auto &e : adj[cur]) {
            if (vst[e]) continue;
            cur = e;
        }
    }
    for (int i = pow2-1; i > 0; i--) {
        segMin[i] = min(segMin[2*i], segMin[2*i+1]);
        segMax[i] = max(segMax[2*i], segMax[2*i+1]);
    }

    vector<int> res(q);
    while (q--) {
        ll s = revA[S[q]];
        ll e = revA[E[q]];
        ll l = L[q], r = R[q];
        res[q] = s < e ? solve(s, e, l, r) : solveRev(s, e, l, r);
    }
    return res;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 173 ms 36296 KB Output is correct
2 Correct 206 ms 44816 KB Output is correct
3 Correct 172 ms 44676 KB Output is correct
4 Correct 167 ms 44800 KB Output is correct
5 Correct 230 ms 44668 KB Output is correct
6 Correct 181 ms 44740 KB Output is correct
7 Correct 174 ms 44744 KB Output is correct
8 Correct 173 ms 44804 KB Output is correct
9 Correct 149 ms 44740 KB Output is correct
10 Correct 145 ms 44668 KB Output is correct
11 Correct 157 ms 44792 KB Output is correct
12 Correct 149 ms 44804 KB Output is correct
13 Correct 159 ms 44740 KB Output is correct
14 Correct 159 ms 44672 KB Output is correct
15 Correct 190 ms 44680 KB Output is correct
16 Correct 176 ms 44740 KB Output is correct
17 Correct 187 ms 44676 KB Output is correct

Subtask #4
0 / 51.0

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