제출 #691739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
691739		Valera_Grinenko	동기화 (JOI13_synchronization)	C++17	100 / 100	417 ms	36288 KiB

synchronization

//#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40