oj.uz

Submission #208230

# Submission time Handle Problem Language Result Execution time Memory
208230 2020-03-10T11:01:11 Z balbit Synchronization (JOI13_synchronization) C++14
100 / 100
 296 ms 34528 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1<<29;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;


void GG(){cout<<"-1\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b) % mo;
}

const int maxn = 1e5+5;

struct BIT{
    vector<int> s;
    int mymax;
    int QU(int e) {
        int re = 0;
        for (++e; e>0; e-=e&-e) re += s[e];
        return re;
    }
    void MO(int e, int v) {
        for (++e; e<mymax; e+=e&-e) s[e] += v;
    }
    void mk(int n) {
        s.resize(n+1,0); mymax = n+1;
    }
    BIT(){
    }
};

int head[maxn], val[maxn], par[maxn], sz[maxn], dep[maxn], ans[maxn];
BIT bb[maxn];
int fa [20] [maxn];
vector<int> g[maxn];

void dfs(int v, int p) {
    sz[v] = 1;
    for (int u : g[v]) {
        if (u!=p) {
            fa[0][u] = v;
            dep[u] = dep[v] + 1;
            dfs(u,v);
            sz[v] += sz[u];
        }
    }
}
void dfs2(int v, int p) {
    int mxsz = 0, mxc = -1;
    for (int u : g[v]) {
        if (u!=p) {
            if (sz[u] > mxsz) mxsz = sz[u], mxc = u;
        }
    }
    for (int u : g[v]) {
        if (u == p) continue;
        if (u == mxc)
            head[u] = head[v];
        else
            head[u] = u;
        dfs2(u,v);
    }
    if (SZ(g[v] ) == 1 && v!=p) {
        bb[head[v]] . mk(dep[v] - dep[head[v]] + 1);
    }
}
int kth(int a, int k) {
    for (int j = 0; k>0; ++j, k/=2) {
        if (k&1) {
            a = fa[j][a];
        }
    }
    return a;
}
int get(int v) {
    int h = head[v];
//    bug("getting",v,h,dep[v],dep[h]);
    if ( bb[h]. QU(dep[v] - dep[h]) == dep[v] - dep[h] + 1) {
//        bug(bb[h].QU(dep[v] - dep[h]), dep[v], dep[h]);
        return get(fa[0][h]);
    }
    int l = 0, r = dep[v] - dep[h];
//    bug(l,r);
    while (l!=r) {
        int m = (l+r)/2;
//        bug(l,r);
        if (bb[h].QU(r) - bb[h].QU(m) != r - m) {
            l = m+1;
        }else{
            r = m;
        }
    }
//    bug(l,dep[v],dep[h]);
    return kth(v,dep[v] - (l + dep[h]));
}

int nw[maxn];

signed main(){
    IOS();
//    freopen ("input.in","r",stdin);
    int n, m, q; cin>>n>>m>>q;
    vector<pii> Ed;
    vector<int> state(n-1); // 0 is off, 1 is on
    for (int i = 0; i<n-1; i++) {
        int a, b; cin>>a>>b;
        --a; --b;
        Ed.pb({a,b});
        g[a].pb(b); g[b].pb(a);
    }
    dfs(0,0);
    for (int j = 1; j<20; ++j) {
        for (int i = 0; i<n; i++) {
            fa[j][i] = fa[j-1][fa[j-1][i]];
        }
    }
    fill(nw, nw+n, 1);
    fill(val, val+n,1);
    dfs2(0,0);
    for (int i = 0; i<n; i++) bug(i,dep[i],fa[0][i]);
    bug("OK");
    while (m--) {
        int id; cin>>id; --id;
        int a = Ed[id].f, b = Ed[id].s;
        if (dep[a] < dep[b]) swap(a,b); // a is deeper
        int h = head[a];
        if (!state[id]) { // add edge
//            bug(a,b,h,dep[a]- dep[h]);
            bb[h].MO(dep[a] - dep[h], 1);
            int tp = get(a);
            bug(tp);
            val[tp] += nw[a];
            nw[tp] += nw[a];
            nw[a] = 0;
        }else{
            int tp = get(a);
            bug(tp);
            bb[h].MO(dep[a] - dep[h], -1);
            val[a] = val[tp];
        }
        state[id] ^= 1;
    }
    while (q--) {
        int x; cin>>x; --x;
        cout<<val[get(x)] << endl;
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5880 KB Output is correct
2 Correct 8 ms 5880 KB Output is correct
3 Correct 8 ms 5880 KB Output is correct
4 Correct 8 ms 5880 KB Output is correct
5 Correct 8 ms 5884 KB Output is correct
6 Correct 9 ms 6136 KB Output is correct
7 Correct 18 ms 7672 KB Output is correct
8 Correct 18 ms 7800 KB Output is correct
9 Correct 17 ms 7672 KB Output is correct
10 Correct 193 ms 23916 KB Output is correct
11 Correct 188 ms 23916 KB Output is correct
12 Correct 211 ms 33628 KB Output is correct
13 Correct 126 ms 25324 KB Output is correct
14 Correct 174 ms 23424 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 29396 KB Output is correct
2 Correct 105 ms 29164 KB Output is correct
3 Correct 126 ms 33004 KB Output is correct
4 Correct 131 ms 33004 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5880 KB Output is correct
2 Correct 8 ms 5880 KB Output is correct
3 Correct 8 ms 5880 KB Output is correct
4 Correct 9 ms 6056 KB Output is correct
5 Correct 8 ms 5880 KB Output is correct
6 Correct 9 ms 6136 KB Output is correct
7 Correct 27 ms 8824 KB Output is correct
8 Correct 267 ms 34412 KB Output is correct
9 Correct 288 ms 34528 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 34412 KB Output is correct
2 Correct 215 ms 34088 KB Output is correct
3 Correct 205 ms 34156 KB Output is correct
4 Correct 219 ms 34284 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5880 KB Output is correct
2 Correct 9 ms 5880 KB Output is correct
3 Correct 8 ms 5880 KB Output is correct
4 Correct 8 ms 6008 KB Output is correct
5 Correct 11 ms 6164 KB Output is correct
6 Correct 20 ms 7800 KB Output is correct
7 Correct 227 ms 24792 KB Output is correct
8 Correct 296 ms 34400 KB Output is correct
9 Correct 158 ms 26604 KB Output is correct
10 Correct 191 ms 24684 KB Output is correct
11 Correct 151 ms 30700 KB Output is correct
12 Correct 147 ms 30572 KB Output is correct
13 Correct 207 ms 34156 KB Output is correct