oj.uz

Submission #1047529

# Submission time Handle Problem Language Result Execution time Memory
1047529 2024-08-07T13:54:02 Z vladilius Synchronization (JOI13_synchronization) C++17
100 / 100
 139 ms 23284 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>

struct ST{
    vector<int> t;
    int n;
    ST(int ns){
        n = ns;
        t.resize(4 * n);
    }
    void upd(int v, int tl, int tr, int& p, bool& k){
        if (tl == tr){
            t[v] = k;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            upd(vv, tl, tm, p, k);
        }
        else {
            upd(vv + 1, tm + 1, tr, p, k);
        }
        t[v] = min(t[vv], t[vv + 1]);
    }
    void upd(int p, bool k){
        upd(1, 1, n, p, k);
    }
    vector<arr3> all;
    void dec(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            all.pb({v, tl, tr});
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        dec(vv + 1, tm + 1, tr, l, r);
        dec(vv, tl, tm, l, r);
    }
    int find(int v, int tl, int tr){
        if (tl == tr) return tl;
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (!t[vv + 1]) return find(vv + 1, tm + 1, tr);
        return find(vv, tl, tm);
    }
    int find(int l, int r){
        all.clear();
        dec(1, 1, n, l, r);
        for (auto [v, tl, tr]: all){
            if (!t[v]){
                return find(v, tl, tr);
            }
        }
        return 0;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, q; cin>>n>>m>>q;
    vector<int> g[n + 1];
    vector<pii> ed = {{}};
    for (int i = 1; i < n; i++){
        int x, y; cin>>x>>y;
        ed.pb({x, y});
        g[x].pb(y);
        g[y].pb(x);
    }
    
    vector<int> sz(n + 1), h(n + 1), d(n + 1), p(n + 1);
    function<void(int, int)> fill = [&](int v, int pr){
        p[v] = pr;
        sz[v] = 1;
        d[v] = d[pr] + 1;
        for (int i: g[v]){
            if (i == pr) continue;
            fill(i, v);
            if (sz[i] > sz[h[v]]){
                h[v] = i;
            }
            sz[v] += sz[i];
        }
    };
    fill(1, 0);
    
    vector<int> head(n + 1), pos(n + 1);
    int timer = 0;
    function<void(int, int)> fill_hld = [&](int v, int k){
        head[v] = k;
        pos[v] = ++timer;
        if (!h[v]) return;
        fill_hld(h[v], k);
        for (int i: g[v]){
            if (pos[i]) continue;
            fill_hld(i, i);
        }
    };
    fill_hld(1, 1);
    
    vector<int> inv(n + 1);
    for (int i = 1; i <= n; i++) inv[pos[i]] = i;
    
    for (int i = 1; i < ed.size(); i++){
        if (d[ed[i].ff] > d[ed[i].ss]){
            swap(ed[i].ff, ed[i].ss);
        }
    }
    
    vector<bool> used(n + 1);
    vector<int> last(n + 1), out(n + 1, 1);
    
    ST T(n);
    auto get = [&](int v){
        while (true){
            int u = T.find(pos[head[v]], pos[v]);
            if (u > 0) return inv[u];
            v = p[head[v]];
        }
    };
    
    while (m--){
        int p; cin>>p;
        auto [u, v] = ed[p];
        if (used[p]){
            out[v] = last[v] = out[get(u)];
            T.upd(pos[v], 0);
        }
        else {
            out[get(u)] += (out[v] - last[v]);
            T.upd(pos[v], 1);
        }
        used[p] = !used[p];
    }
    while (q--){
        int x; cin>>x;
        cout<<out[get(x)]<<"\n";
    }
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for (int i = 1; i < ed.size(); i++){
      |                     ~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 572 KB Output is correct
7 Correct 8 ms 1628 KB Output is correct
8 Correct 7 ms 1628 KB Output is correct
9 Correct 7 ms 1624 KB Output is correct
10 Correct 94 ms 11724 KB Output is correct
11 Correct 104 ms 11920 KB Output is correct
12 Correct 81 ms 22732 KB Output is correct
13 Correct 84 ms 11984 KB Output is correct
14 Correct 62 ms 11712 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 17352 KB Output is correct
2 Correct 48 ms 17124 KB Output is correct
3 Correct 42 ms 22736 KB Output is correct
4 Correct 42 ms 22736 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 8 ms 2904 KB Output is correct
8 Correct 100 ms 22908 KB Output is correct
9 Correct 99 ms 22976 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 22984 KB Output is correct
2 Correct 56 ms 23144 KB Output is correct
3 Correct 58 ms 23244 KB Output is correct
4 Correct 67 ms 23284 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 536 KB Output is correct
6 Correct 11 ms 1644 KB Output is correct
7 Correct 118 ms 11976 KB Output is correct
8 Correct 98 ms 22976 KB Output is correct
9 Correct 81 ms 12732 KB Output is correct
10 Correct 139 ms 12488 KB Output is correct
11 Correct 69 ms 17860 KB Output is correct
12 Correct 69 ms 18036 KB Output is correct
13 Correct 58 ms 23236 KB Output is correct