제출 #1295762

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

synchronization

#include<bits/stdc++.h>
using namespace std;

// Extra functionality :
// *st.find_by_order(index) = value at index
// st.order_of_key(value) = number of elements strictly less than value

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

#define ll long long
#define lld long double
#define vll vector<long long>
#define pll pair<long long, long long>
#define vvll vector<vll>
#define vvvll vector<vvll>
#define ar array
#define F first
#define S second

#define all(v) v.begin(),v.end()
#define range(v, i, j) v.begin()+i, v.begin()+j+1
#define For(i, a, b) for(long long i = (a); i <= (b); ++(i))
#define L(i, a, b) for(long long i = (a); i <= (b); ++(i))
#define R(i, a, b) for(long long i = (a); i >= (b); --(i))
#define sz(x) (ll)(x.size())
#define extract(m, x) { auto it = (m).find(x); if (it != (m).end()) (m).erase(it); } // set, multiset, map
#define gp " "
#define nl "\n"
#define yes cout<<"YES"<<nl
#define no cout<<"NO"<<nl

#define isSet(x, i) ((x>>i)&1)
#define setbit(x, i) (x | (1LL<<i))
#define resetbit(x, i) (x & (~(1LL << i)))
#define toggleBit(x, i) ((x) ^ (1LL << (i)))
#define getBit(x, i) (((x) >> (i)) & 1)
#define clz(x) __builtin_clzll(x)
#define ctz(x) __builtin_ctzll(x)
#define csb(x) __builtin_popcountll(x)


#ifdef LOCAL
#include "debug.h"
#else
#define deb(...) (void)0
#endif

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int dx4[4] = {0, 0, 1, -1}, dy4[4] = {1, -1, 0, 0};
const int mod = 1e9 + 7;
const int N = 200005; ///////////////////////////////////////
const ll inf = 1e15; /////////////////////////////////////////////

struct Seg{
    struct node{
        ll mn = inf;
        ll mx = -inf;
        ll lazy = 0; // USE INF FOR RANGE ASSIGNMENT *****
        ll sum = 0;
 
        node() {}
        node(ll x) : mn(x), mx(x), sum(x) {}
        void apply(int l, int r, ll y) {
            mn += y; mx += y;
            sum += y * (r - l + 1);
            if(l != r) lazy += y;    // => applied here, but pending in children

            // mn = mx = y;          // for range assignment
            // sum = y * (r - l + 1) // for range assignment
            // if(l != r) lazy = y;  // for range assignment
        }
    };

    int size;
    vector<node> tree;

    Seg(vll & a) {
        ll n = sz(a);
        size = 1; while(size < n) size *= 2;
        tree.assign(2 * size , node()); 

        For(i, 0, n-1) { // leaves (input array) 
            tree[size + i] = a[i];  
        }
        for(ll j = size - 1; j >= 1; j--) { 
            pull(j);
        }
    }

    node unite(node a, node b){ 
        node res;
        res.mn = min(a.mn, b.mn);
        res.mx = max(a.mx, b.mx);
        res.sum = a.sum + b.sum;
        return res;
    }
    void push(int pos, int l, int r){
        if(l == r) return;
        if (tree[pos].lazy != 0) {                          // default lazy
            int mid = (l + r) / 2;
            tree[2*pos].apply(l, mid, tree[pos].lazy);
            tree[2*pos+1].apply(mid+1, r, tree[pos].lazy);
            tree[pos].lazy = 0;                             // default lazy
        }
    }
    void pull(int pos){
        tree[pos] = unite(tree[pos * 2], tree[pos * 2 + 1]);
    }


    node query(int ql, int qr){
        return query(1, 0, size-1, ql, qr); 
    }
    node query(int pos, int l, int r, int ql, int qr) {
        push(pos, l, r);
        if (l >= ql && r <= qr) { return tree[pos];}
        if (qr < l || ql > r) return node();
        int mid = (l + r) / 2;
        node res;
        if (qr <= mid) res = query(2 * pos, l, mid, ql, qr);
        else if (ql > mid) res = query(pos * 2 + 1, mid + 1, r, ql, qr);
        else res = unite(query(pos * 2, l, mid, ql, qr), 
                            query(pos * 2 + 1, mid + 1, r,  ql, qr));
        return res;
    }


    void modify(int ql, int qr, ll y) {
        modify(1, 0, size-1, ql, qr, y); 
    }
    void modify(int pos, int l, int r, int ql, int qr, ll y){
        if(ql > r || qr < l) return;
        push(pos, l, r);
        if (l >= ql && r <= qr){
            tree[pos].apply(l, r, y);
            return;
        }
        int mid = (l + r) / 2;
        if (ql <= mid) modify(2 * pos, l, mid, ql, qr, y);
        if (qr > mid) modify(2 * pos + 1, mid + 1, r, ql, qr, y);
        pull(pos);
    }
};

void prep(){
    
}

ll n, m, x, y, z, q, k, u, v, w;

vvll gr(N);
vector<ar<ll,2>> edges(N);
ll timer = -1;
vll in(N), out(N);
vvll lift(N, vll(20));
vll depth(N);

void euler_tour(ll node, ll par, ll d) {
    depth[node] = d;

    lift[node][0] = par;
    for(ll j = 1; j < 20; ++j) {
        lift[node][j] = lift[ lift[node][j-1] ][j-1];
    }

    in[node] = ++timer;
    for(ll ch : gr[node]) {
        if(ch == par) continue;
        euler_tour(ch, node, d+1);
    }
    out[node] = timer;
}   

vll prevv(N), now(N, 1);
bool ispres[N];
void solve(int tcase){
    
    // testcases ?

    // cleanup ?

    cin >> n >> m >> q;
    L(i, 1, n-1) {
        cin >> u >> v; gr[u].push_back(v); gr[v].push_back(u);
        edges[i] = {u, v};
    }

    euler_tour(1,0, 0);
    vll khali(n+1);
    Seg seg(khali); // will hold no. of DISCONNECTED edges on path to root
    L(i, 1, n) seg.modify(in[i], in[i], depth[i]);

    auto find_root = [&](ll y) {
        R(j,19,0) {
            ll x = lift[y][j];
            ll disc_x = seg.query(in[x],in[x]).sum; // or min/max
            ll disc_y = seg.query(in[y],in[y]).sum;
            if(disc_y == disc_x) { // x is in y's component   
                y = x;
            }
        }
        return y;
    };

    ll e;
    while(m--) {
        cin >> e; auto [u, v] = edges[e];

        if(!ispres[e]) {
            ispres[e] = 1;

            // make v the one below
            if(lift[u][0] == v) swap(u,v);

            ll root = find_root(u);
            now[root] += now[v] - prevv[v];

            seg.modify(in[v], out[v], -1);

        } else {
            ispres[e] = 0;

            // make v the one below
            if(lift[u][0] == v) swap(u,v);

            ll root = find_root(v); // or u
            now[v] = now[root];
            prevv[v] = now[v];

            seg.modify(in[v], out[v], +1);
        }
    }

    while(q--) {
        cin >> u; cout << now[find_root(u)] << nl;
    }

}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    prep();
    int tcase = 1;
    // int t; cin >> t; for(; tcase <= t; ++tcase)
    solve(tcase);
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40