oj.uz

Submission #691739

# Submission time Handle Problem Language Result Execution time Memory
691739 2023-01-31T13:45:21 Z Valera_Grinenko Synchronization (JOI13_synchronization) C++17
100 / 100
 417 ms 36288 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]) {
            ans[rootx] += ans[y] - last_sync[y];
            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 8 ms 20180 KB Output is correct
3 Correct 9 ms 20180 KB Output is correct
4 Correct 11 ms 20180 KB Output is correct
5 Correct 10 ms 20204 KB Output is correct
6 Correct 10 ms 20328 KB Output is correct
7 Correct 30 ms 20948 KB Output is correct
8 Correct 28 ms 20900 KB Output is correct
9 Correct 34 ms 20948 KB Output is correct
10 Correct 313 ms 27868 KB Output is correct
11 Correct 331 ms 27748 KB Output is correct
12 Correct 172 ms 35500 KB Output is correct
13 Correct 147 ms 27632 KB Output is correct
14 Correct 203 ms 27180 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 29452 KB Output is correct
2 Correct 93 ms 31248 KB Output is correct
3 Correct 76 ms 34920 KB Output is correct
4 Correct 77 ms 34836 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20244 KB Output is correct
2 Correct 10 ms 20280 KB Output is correct
3 Correct 9 ms 20284 KB Output is correct
4 Correct 8 ms 20284 KB Output is correct
5 Correct 8 ms 20284 KB Output is correct
6 Correct 9 ms 20436 KB Output is correct
7 Correct 21 ms 21812 KB Output is correct
8 Correct 167 ms 36288 KB Output is correct
9 Correct 193 ms 36252 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 33408 KB Output is correct
2 Correct 103 ms 35940 KB Output is correct
3 Correct 102 ms 35996 KB Output is correct
4 Correct 111 ms 36000 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20180 KB Output is correct
2 Correct 8 ms 20180 KB Output is correct
3 Correct 8 ms 20180 KB Output is correct
4 Correct 9 ms 20232 KB Output is correct
5 Correct 10 ms 20316 KB Output is correct
6 Correct 36 ms 21044 KB Output is correct
7 Correct 417 ms 28556 KB Output is correct
8 Correct 173 ms 36256 KB Output is correct
9 Correct 161 ms 28696 KB Output is correct
10 Correct 307 ms 28376 KB Output is correct
11 Correct 128 ms 32636 KB Output is correct
12 Correct 123 ms 32668 KB Output is correct
13 Correct 103 ms 35996 KB Output is correct