oj.uz

Submission #479239

# Submission time Handle Problem Language Result Execution time Memory
479239 2021-10-11T00:36:31 Z bonopo Synchronization (JOI13_synchronization) C++17
100 / 100
 855 ms 21000 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define rc (i<<1)|1
#define lc (i<<1)
#define el "\n"
#define f first
#define s second
 
typedef long long ll;
const int MM=1e5+5, MOD=1e9+7, LOG=18;
int N, M, Q, pa[LOG][MM], bit[MM], st[MM], in[MM], ot[MM], c[MM], l[MM], dt;
pair<int,int> edg[MM];
vector<int> adj[MM];
 
void upd(int idx, int v) {
    for(; idx<MM; idx+=idx&-idx) bit[idx]+=v;
}
 
int qry(int idx) {
    int ret=0;
    for(; idx>=1; idx-=idx&-idx) ret+=bit[idx];
    return ret;
}
 
void dfs(int u, int fa) {
    pa[0][u]=fa; in[u]=++dt;
    for(int i=1; i<LOG; ++i) {
        pa[i][u]=pa[i-1][pa[i-1][u]]; }
    for(int &v:adj[u]) if(v!=fa) {
        dfs(v, u); }
    ot[u]=dt+1;
}
 
int up(int u, int k) {
    for(int i=LOG-1; i>=0; --i) if(k>=(1<<i)) u=pa[i][u], k-=1<<i;
    return u;
}
 
int rt(int u) {
    int lo=0, hi=N, mid, ret=u;
    while(lo<=hi) {
        mid=lo+hi>>1; int nx=up(u, mid);
        if(qry(in[u])-qry(in[nx])==mid) ret=nx, lo=mid+1;
        else hi=mid-1;
    }
    return ret;
}
 
int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>N>>M>>Q;
    fill(c+1, c+N+1, 1);
    for(int i=1; i<N; ++i) {
        int u, v; cin>>u>>v;
        adj[u].pb(v), adj[v].pb(u);
        edg[i]={u,v};
    }
 
    dfs(1, 1);
    for(int i=1, x; i<=M; ++i) {
        cin>>x;
 
        int u=edg[x].f, v=edg[x].s;
        if(in[u]>in[v]) swap(u, v);
 
        if(st[x]) {
            // turn edge off
            upd(in[v], -1); upd(ot[v],  1);
            u=rt(u); c[v]=l[v]=c[u];
        } else {
            // turn edge on
            upd(in[v],  1); upd(ot[v], -1);
            u=rt(u); c[u]+=c[v]-l[v];
        }
 
        st[x]^=1;
    }
 
    for(int i=1, x; i<=Q; ++i) {
        cin>>x; x=rt(x);
        cout<<c[x]<<el;
    }
}
 
// MM

Compilation message

synchronization.cpp: In function 'int rt(int)':
synchronization.cpp:45:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |         mid=lo+hi>>1; int nx=up(u, mid);
      |             ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 3 ms 2892 KB Output is correct
7 Correct 21 ms 4044 KB Output is correct
8 Correct 23 ms 4136 KB Output is correct
9 Correct 21 ms 4044 KB Output is correct
10 Correct 425 ms 16180 KB Output is correct
11 Correct 452 ms 16060 KB Output is correct
12 Correct 702 ms 20696 KB Output is correct
13 Correct 170 ms 16312 KB Output is correct
14 Correct 268 ms 15672 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 18148 KB Output is correct
2 Correct 189 ms 18068 KB Output is correct
3 Correct 193 ms 20292 KB Output is correct
4 Correct 192 ms 20328 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 4 ms 2892 KB Output is correct
7 Correct 39 ms 4556 KB Output is correct
8 Correct 828 ms 20848 KB Output is correct
9 Correct 834 ms 20876 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 20768 KB Output is correct
2 Correct 331 ms 20856 KB Output is correct
3 Correct 332 ms 20876 KB Output is correct
4 Correct 326 ms 20804 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 4 ms 2892 KB Output is correct
6 Correct 29 ms 4160 KB Output is correct
7 Correct 566 ms 16312 KB Output is correct
8 Correct 847 ms 20808 KB Output is correct
9 Correct 271 ms 16828 KB Output is correct
10 Correct 363 ms 16324 KB Output is correct
11 Correct 307 ms 18756 KB Output is correct
12 Correct 306 ms 18884 KB Output is correct
13 Correct 349 ms 21000 KB Output is correct