oj.uz

Submission #479238

# Submission time Handle Problem Language Result Execution time Memory
479238 2021-10-11T00:36:01 Z bonopo Synchronization (JOI13_synchronization) C++17
0 / 100
 948 ms 21300 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=19;
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<2*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
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 3 ms 2892 KB Output is correct
7 Correct 25 ms 4208 KB Output is correct
8 Correct 22 ms 4172 KB Output is correct
9 Correct 24 ms 4204 KB Output is correct
10 Correct 522 ms 16352 KB Output is correct
11 Correct 455 ms 16572 KB Output is correct
12 Correct 723 ms 21036 KB Output is correct
13 Correct 175 ms 16704 KB Output is correct
14 Incorrect 251 ms 16068 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 212 ms 18628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
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 40 ms 4652 KB Output is correct
8 Incorrect 948 ms 21236 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 945 ms 21300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
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 32 ms 4200 KB Output is correct
7 Incorrect 574 ms 16676 KB Output isn't correct
8 Halted 0 ms 0 KB -