oj.uz

Submission #691740

# Submission time Handle Problem Language Result Execution time Memory
691740 2023-01-31T13:47:00 Z Valera_Grinenko Synchronization (JOI13_synchronization) C++17
100 / 100
 427 ms 33740 KB 
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#ifdef __APPLE__

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <immintrin.h>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>

#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#if __APPLE__
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define D while (false)
#define LOG(...)
#endif

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct stmnmx {
    static const int Nmax = 5e5 + 42;
    int Nst;
    pair<int, int> st[Nmax * 4];
    pair<int, int> id = {-1e9, -1e9};
#define mnmx max

    pair<int, int> get_(int l, int r, int v, int tl, int tr) {
        if (l > r) return id;
        if (l == tl && r == tr) return st[v];
        int tm = ((tl + tr) >> 1);
        return mnmx(get_(l, min(r, tm), (v << 1), tl, tm), get_(max(l, tm + 1), r, (v << 1) + 1, tm + 1, tr));
    }

    pair<int, int> get(int l, int r) {
        return get_(l, r, 1, 0, Nst - 1);
    }

    void upd_(int pos, pair<int, int> new_v, int v, int tl, int tr) {
        if (tl == tr) st[v] = new_v;
        else {
            int tm = ((tl + tr) >> 1);
            if (pos <= tm) upd_(pos, new_v, (v << 1), tl, tm);
            else upd_(pos, new_v, (v << 1) + 1, tm + 1, tr);
            st[v] = mnmx(st[(v << 1)], st[(v << 1) + 1]);
        }
    }

    void upd(int pos, pair<int, int> new_v) {
        return upd_(pos, new_v, 1, 0, Nst - 1);
    }
};


stmnmx st;

struct HLD {
    static const int maxN = 1e5 + 42;
    vector<int> g[maxN];
    int head[maxN] = {}, parent[maxN] = {}, depth[maxN] = {}, subt[maxN] = {};
    int pos[maxN] = {};
    int curpos = 0;
    bool VALS_IN_EDGES = 0;

    void init(int root) {
        parent[root] = depth[root] = curpos = 0;
        predfs(root);
        head[root] = root;
        dfsHLD(root);
    }

    void add_edge(int a, int b) {
        g[a].pb(b);
        g[b].pb(a);
    }

    void predfs(int v) {
        subt[v] = 1;
        for (auto &to: g[v]) {
            parent[to] = v;
            depth[to] = depth[v] + 1;
            g[to].erase(find(all(g[to]), v));
            predfs(to);
            subt[v] += subt[to];
            if (subt[to] > subt[g[v][0]]) swap(g[v][0], to);
        }
    }

    void dfsHLD(int v) {
        pos[v] = curpos++;
        for (auto &to: g[v]) {
            head[to] = (to == g[v][0] ? head[v] : to);
            dfsHLD(to);
        }
    }

    int lca(int a, int b) {
        for (; head[a] != head[b]; b = parent[head[b]]) {
            if (depth[head[a]] > depth[head[b]]) swap(a, b);
        }
        if (depth[a] > depth[b]) swap(a, b);
        return a;
    }

    pair<int, int> query_path(int a, int b) {
        pair<int, int> res = st.id;
        for (; head[a] != head[b]; b = parent[head[b]]) {
            if (depth[head[a]] > depth[head[b]]) swap(a, b);
            res = max(res, st.get(pos[head[b]], pos[b]));
        }
        if (depth[a] > depth[b]) swap(a, b);
        res = max(res, st.get(pos[a] + VALS_IN_EDGES, pos[b]));
        return res;
    }
};


void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int, int> > edges(n - 1);
    HLD hld;
    for(int i = 0; i < n - 1; i++) {
        cin >> edges[i].fi >> edges[i].se;
        edges[i].fi--; edges[i].se--;
        hld.add_edge(edges[i].fi, edges[i].se);
    }
    hld.init(0);
    st.Nst = n;
    for(int i = 0; i < n; i++) {
        st.upd(hld.pos[i], {hld.depth[i], i});
    }
    vector<int> active(n - 1);
    vector<int> ans(n, 1), last_sync(n);
    while(m--) {
        int edg; cin >> edg; edg--;
        int x = edges[edg].fi, y = edges[edg].se;
        if(hld.depth[x] > hld.depth[y]) swap(x, y);
        int rootx = hld.query_path(0, x).se;
        if(!active[edg]) {
            int nval = ans[rootx] + ans[y] - last_sync[y];
            ans[rootx] = ans[y] = last_sync[y] = nval;
            st.upd(hld.pos[y], st.id);
        } else {
            ans[y] = last_sync[y] = ans[rootx];
            st.upd(hld.pos[y], {hld.depth[y], y});
        }
        active[edg] ^= 1;
    }
    while(q--) {
        int v; cin >> v; v--; cout << ans[hld.query_path(0, v).se] << '\n';
    }
}

signed main() {
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;

    //cin >> t;

    while (t--) solve();

}

/*
KIVI
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20180 KB Output is correct
2 Correct 9 ms 20164 KB Output is correct
3 Correct 8 ms 20180 KB Output is correct
4 Correct 8 ms 20180 KB Output is correct
5 Correct 9 ms 20176 KB Output is correct
6 Correct 9 ms 20308 KB Output is correct
7 Correct 27 ms 20692 KB Output is correct
8 Correct 28 ms 20720 KB Output is correct
9 Correct 28 ms 20692 KB Output is correct
10 Correct 327 ms 25420 KB Output is correct
11 Correct 336 ms 25360 KB Output is correct
12 Correct 140 ms 33192 KB Output is correct
13 Correct 120 ms 25740 KB Output is correct
14 Correct 191 ms 25508 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 29484 KB Output is correct
2 Correct 90 ms 29260 KB Output is correct
3 Correct 77 ms 33192 KB Output is correct
4 Correct 78 ms 33112 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20232 KB Output is correct
2 Correct 8 ms 20180 KB Output is correct
3 Correct 9 ms 20180 KB Output is correct
4 Correct 8 ms 20180 KB Output is correct
5 Correct 9 ms 20292 KB Output is correct
6 Correct 10 ms 20376 KB Output is correct
7 Correct 24 ms 21576 KB Output is correct
8 Correct 165 ms 33328 KB Output is correct
9 Correct 159 ms 33368 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 33356 KB Output is correct
2 Correct 100 ms 33676 KB Output is correct
3 Correct 102 ms 33712 KB Output is correct
4 Correct 101 ms 33740 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20244 KB Output is correct
2 Correct 8 ms 20180 KB Output is correct
3 Correct 8 ms 20180 KB Output is correct
4 Correct 8 ms 20192 KB Output is correct
5 Correct 10 ms 20240 KB Output is correct
6 Correct 34 ms 20820 KB Output is correct
7 Correct 427 ms 25736 KB Output is correct
8 Correct 216 ms 33360 KB Output is correct
9 Correct 154 ms 26320 KB Output is correct
10 Correct 282 ms 26148 KB Output is correct
11 Correct 116 ms 30028 KB Output is correct
12 Correct 118 ms 29996 KB Output is correct
13 Correct 103 ms 33716 KB Output is correct