Submission #1083947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083947		underwaterkillerwhale	Synchronization (JOI13_synchronization)	C++17	20 / 100	428 ms	31164 KiB

synchronization

#include <bits/stdc++.h>
#define ll              long long
#define pii             pair<int,int>
#define pll             pair<ll,ll>
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
#define iter(id, v)     for(auto id : v)
#define fs              first
#define se              second
#define MP              make_pair
#define pb              push_back
#define bit(msk, i)     ((msk >> i) & 1)
#define SZ(v)           (ll)v.size()
#define ALL(v)          v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const ll INF = 1e18;
const ll BASE = 137;
const int szBL = 350;

int n, Q, K;
pii ed[N];
vector<int> ke[N];
int val[N], pVal[N];

int pa[N], nC[N], high[N], par[N][25];
int Head[N], ein[N];

bool stt[N];

struct Segment_Tree {
    int m;
    bool st[N << 2];

    void init (int n) {
        m = n;
    }

    void update (int id, int l, int r, int pos) {
        if (l > pos || r < pos) return;
        if (l == r) {
            st[id] ^= 1;
            return;
        }
        int mid = l + r >> 1;
        update (id << 1, l, mid, pos);
        update (id << 1 | 1, mid + 1, r, pos);
        st[id] = st[id << 1] & st[id << 1 | 1];
    }
    int get (int id, int l, int r, int u, int v) {
        if (l > v|| r < u) return 1;
        if (l >= u && r <= v) return st[id];
        int mid = l + r >> 1;
        return get (id << 1, l, mid, u, v) & get (id << 1 | 1, mid + 1, r, u, v);
    }

    void update (int pos) {
        update (1, 1, m, pos);
    }
    int get (int u, int v ) {
        return get (1, 1, m, u, v);
    }
}ST;

void pdfs (int u, int p) {
    high[u] = high[p] + 1;
    pa[u] = p;
    par[u][0] = p;
    rep (i, 1, 20) par[u][i] = par[par[u][i - 1]][i - 1];
    nC[u] = 1;
    iter (&v, ke[u]) {
        if (v != p) {
            pdfs(v, u);
            nC[u] += nC[v];
        }
    }
}

void hld (int u, int p) {
    static int time_dfs = 0;
    Head[u] = p;
    ein[u] = ++time_dfs;
    int mxV = -1;
    iter (&v, ke[u]) if (v != pa[u] && (mxV == -1 || nC[v] > nC[mxV])) mxV = v;
    if (mxV != -1) hld(mxV, p);
    iter (&v, ke[u]) {
        if (v == pa[u] || v == mxV) continue;
        hld(v, v);
    }
}

int root (int u) {
    while (u != 0) {
        bool cnc = ST.get(ein[Head[u]], ein[u]);
        if (cnc == 0) {
            if (ST.get(ein[u], ein[u]) == 0) return u;
            reb (i, 20, 0) {
                int cur = par[u][i];
                if (high[cur] >= high[Head[u]] && ST.get(ein[cur], ein[u])) {
                    u = cur;
                }
            }
            return pa[u];
        }
        u = pa[Head[u]];
    }
    assert(0);
}

int getVal (int u) {
    return val[root(u)];
}

void Connect (int u, int v) {
    if (high[u] > high[v]) swap(u, v);
    int delta = val[v] - pVal[v];
//    cout << u <<" "<<v<<" "<<getVal(u)<<" "<<getVal(v)<<"\n";
    val[root(u)] += delta;
    ST.update (ein[v]);
}

void Detach (int u, int v) {
    if (high[u] > high[v]) swap(u, v);
    pVal[u] = pVal[v] = val[u] = val[v] = getVal(u);
    ST.update (ein[v]);
}

void solution () {
    cin >> n >> Q >> K;
    rep (i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        ed[i] = MP(u, v);
        ke[u].pb(v);
        ke[v].pb(u);
    }
    rep (i, 1, n) val[i] = 1;
    pdfs(1, 0);
    hld(1, 1);
    ST.init(n);
//    return;
    rep (i, 1, Q) {
        int p;
        cin >> p;
        stt[p] ^= 1;
        if (stt[p] == 1) {
            Connect(ed[p].fs, ed[p].se);
        }
        else {
            Detach(ed[p].fs, ed[p].se);
        }
    }
    rep (i, 1, K) {
        int X;
        cin >> X;
        cout << getVal(X) <<"\n";
    }

}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +4
mình có muốn dùng mảng này không?
100 0 150
4 82 9 38 25 3 48 61 2 39 42 73 64 23 58 42 39 32 34 90 45 12 75 98 90 36 62 97 86 89 69 56 70 44 94 95 47 7 22 16 46 64 89 77 53 46 18 92 45 18 48 56 30 89 20 86 24 48 83 76 36 17 31 72 62 91 32 75 98 54 91 10 85 80 87 37 92 71 96 2 89 9 59 86 98 79 71 21 26 19 63 28 37 94 100 65 50 31 39 13

*/

Compilation message (stderr)

synchronization.cpp: In member function 'void Segment_Tree::update(int, int, int, int)':
synchronization.cpp:51:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         int mid = l + r >> 1;
      |                   ~~^~~
synchronization.cpp: In member function 'int Segment_Tree::get(int, int, int, int, int)':
synchronization.cpp:59:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |         int mid = l + r >> 1;
      |                   ~~^~~

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