oj.uz

Submission #1047521

# Submission time Handle Problem Language Result Execution time Memory
1047521 2024-08-07T13:50:29 Z vladilius Synchronization (JOI13_synchronization) C++17
100 / 100
 124 ms 24264 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
#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:111: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]
  111 |     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 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 348 KB Output is correct
7 Correct 8 ms 1844 KB Output is correct
8 Correct 7 ms 1772 KB Output is correct
9 Correct 8 ms 1832 KB Output is correct
10 Correct 97 ms 14104 KB Output is correct
11 Correct 95 ms 14096 KB Output is correct
12 Correct 85 ms 23392 KB Output is correct
13 Correct 66 ms 14024 KB Output is correct
14 Correct 66 ms 13612 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 18632 KB Output is correct
2 Correct 49 ms 18384 KB Output is correct
3 Correct 46 ms 22752 KB Output is correct
4 Correct 44 ms 22720 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 344 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 10 ms 2788 KB Output is correct
8 Correct 100 ms 24148 KB Output is correct
9 Correct 101 ms 24128 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 24264 KB Output is correct
2 Correct 61 ms 23808 KB Output is correct
3 Correct 62 ms 24040 KB Output is correct
4 Correct 63 ms 23872 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 11 ms 1884 KB Output is correct
7 Correct 124 ms 14916 KB Output is correct
8 Correct 113 ms 24260 KB Output is correct
9 Correct 88 ms 15044 KB Output is correct
10 Correct 118 ms 14788 KB Output is correct
11 Correct 74 ms 19900 KB Output is correct
12 Correct 77 ms 19772 KB Output is correct
13 Correct 63 ms 23900 KB Output is correct