oj.uz

Submission #994557

# Submission time Handle Problem Language Result Execution time Memory
994557 2024-06-08T00:55:10 Z vjudge1 Synchronization (JOI13_synchronization) C++17
30 / 100
 170 ms 15192 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;

const ll MAXN = 1E5+16;
vector <ii> adj[MAXN];

struct Fenwick {
    vll tree;
    ll n;

    Fenwick (ll n): tree(n, 0), n(n) {}

    void update (ll id, ll val) {
        for (; id < n; id |= id+1)
            tree[id] += val;
    }

    ll query (ll ql, ll qr) { return query(qr) - query(ql-1); }
    ll query (ll id) {
        ll ans = 0;
        for (; id >= 0; id &= id+1, id--) ans += tree[id];
        return ans;
    }
};

ii operator+ (const ii a, const ii b) {
    return {
        min(a.first, b.first),
        max(a.second, b.second)
    };
}

struct SegTree {
    vector <ii> tree;
    ll n;

    SegTree (ll n): tree(2*n, { n, -1 }), n(n) {}

    void update (ll id, ll val, bool atF) {
        id += n;
        if (atF) tree[id].first = val;
        else tree[id].second = val;
        for (; id > 1; id >>= 1) {
            tree[id>>1] = tree[id] + tree[id^1];
        }
    }

    ii query (ll ql, ll qr) {
        ii ans = { n, -1 };
        for (ql += n, qr += n+1; ql < qr; ql >>= 1, qr >>= 1) {
            if (ql&1) ans = ans + tree[ql++];
            if (qr&1) ans = ans + tree[--qr];
        }
        return ans;
    }
};

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n, m, Q;
    cin >> n >> m >> Q;
    for (ll i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        u--; v--;
        adj[u].push_back({ v, i });
        adj[v].push_back({ u, i });
    }
    vector <char> isOn(n, false);
    Fenwick ft(n-1);
    SegTree st(n);
    for (ll i = 0; i < n; i++) {
        st.update(i, i, true);
        st.update(i, i, false);
    }
    while (m--) {
        ll at;
        cin >> at;
        at--;
        isOn[at] ^= 1;
        if (!isOn[at]) { ft.update(at, -1); continue; }
        ft.update(at, 1);
        ll f1, l1;
        {ll l = -1, r = at;
        while (l+1 < r) {
            ll mid = ((l+r)>>1);
            if (ft.query(mid, at) == at-mid+1)
                r = mid;
            else
                l = mid;
        }
        f1 = r;}
        {ll l = at, r = n-1;
        while (l+1 < r) {
            ll mid = ((l+r)>>1);
            if (ft.query(at, mid) == mid-at+1)
                l = mid;
            else
                r = mid;
        }
        l1 = l;}
        l1++;
        auto [minN, _1] = st.query(f1, n-1);
        auto [_2, maxN] = st.query(0, l1);
        st.update(l1, minN, true);
        st.update(f1, maxN, false);
    }
    vll ans(n);
    for (ll i = 0; i < n; i++) {
        auto [minN, _1] = st.query(i, n-1);
        auto [_2, maxN] = st.query(0, i);
        ans[i] = maxN-minN+1;
    }
    while (Q--) {
        ll u;
        cin >> u;
        u--;
        cout << ans[u] << '\n';
    }
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 20.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 13 ms 3936 KB Output is correct
8 Correct 170 ms 15172 KB Output is correct
9 Correct 163 ms 15184 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 15192 KB Output is correct
2 Correct 129 ms 14932 KB Output is correct
3 Correct 134 ms 15188 KB Output is correct
4 Correct 134 ms 15188 KB Output is correct

Subtask #5
0 / 40.0

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