oj.uz

Submission #649068

# Submission time Handle Problem Language Result Execution time Memory
649068 2022-10-09T02:47:21 Z AkiYuu Synchronization (JOI13_synchronization) C++17
100 / 100
 592 ms 23808 KB 
/*

Author: AkiYuu
TASK:
LANG: C++14

*/

#include <bits/stdc++.h>
#define task "GROUP"
#define ll long long
#define ld long double
#define pb push_back
#define ffw(i,a,b) for (ll i = a; i <= b; i++)
#define fbw(i,b,a) for (ll i = b; i >= a; i--)
#define adj(v,adj,u) for (auto v : adj[u])
#define rep(i,a) for (auto i : a)
#define reset(a) memset(a, 0, sizeof(a))
#define sz(a) a.size()
#define all(a) a.begin(),a.end()

using namespace std;

void fastio(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
//	freopen(task".inp", "r", stdin);
//	freopen(task".out", "w", stdout);
}

const int mxn = 1e5 + 5;
typedef pair<ll, ll> ii;

vector < int > a[mxn];
int now[mxn], last[mxn];
int up[20][mxn];
int n , m, q;
int tin[mxn], tout[mxn], timer = 0;
bool state[mxn];
int U[mxn], V[mxn];
int BIT[mxn];

void upd(int id, int v ){
    for(id; id <= n + 1; id += id & -id){
        BIT[id] += v;
    }
}

int sum(int id ){
    int res = 0;
    for ( id; id > 0; id -=  id & -id)
        res += BIT[id];
    return res;
}
void dfs(int u, int p){

    tin[u] = ++timer;


    up[0][u] = p;

    adj(v,a,u){
        if ( v == p ) continue;
        dfs(v,u);
    }

    tout[u] = timer;
}


int findlow(int u ){
    int ans = u;
    fbw(i,18,0) if ( sum(tin[up[i][ans]]) == sum(tin[u]) ) ans = up[i][ans];
    return ans;
}

void solve(){
    cin >> n >> m >> q;
    ffw(i,1,n-1){
        int u , v;
        cin >> u >> v;
        U[i] = u;
        V[i] = v;
        a[u].pb(v);
        a[v].pb(u);
    }
    dfs(1,1);

    ffw(k,1,18) ffw(i,1,n) {
        up[k][i] = up[k-1][ up[k-1][i] ];
    }

    ffw(i,1,n){
        now[i] = 1;
        last[i] = 0;
        state[i] = 0;
        upd(tin[i], 1);
        upd(tout[i] + 1, -1);
    }

    while(m--){
        int x;
        cin >> x;
        int u = U[x], v = V[x];
        if ( up[0][u] == v ) swap(u,v);
        if ( state[x] ) {
            now[v] = last[v] = now[ findlow(u) ];
            upd(tin[v], 1);
            upd(tout[v]+1, -1);
        }else {
            now[ findlow(u) ] += now[v] - last[v];
            upd(tin[v], -1);
            upd(tout[v] + 1, 1);
        }

        state[x] ^= 1;
    }

//    ffw(i,1,n) cout << now[i] << ' ';
//    cout << '\n';

    while(q--){

        int u; cin >> u;
        cout << now[ findlow(u) ] << '\n';

    }
}

int main(){
	fastio();
	int t = 1;
//	cin >> t;
	while (t--)
	solve();
}

Compilation message

synchronization.cpp: In function 'void upd(int, int)':
synchronization.cpp:45:9: warning: statement has no effect [-Wunused-value]
   45 |     for(id; id <= n + 1; id += id & -id){
      |         ^~
synchronization.cpp: In function 'int sum(int)':
synchronization.cpp:52:11: warning: statement has no effect [-Wunused-value]
   52 |     for ( id; id > 0; id -=  id & -id)
      |           ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 3 ms 2900 KB Output is correct
7 Correct 19 ms 4308 KB Output is correct
8 Correct 21 ms 4328 KB Output is correct
9 Correct 20 ms 4336 KB Output is correct
10 Correct 449 ms 18456 KB Output is correct
11 Correct 442 ms 18344 KB Output is correct
12 Correct 466 ms 23032 KB Output is correct
13 Correct 98 ms 18368 KB Output is correct
14 Correct 184 ms 17844 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 20524 KB Output is correct
2 Correct 92 ms 20508 KB Output is correct
3 Correct 101 ms 22476 KB Output is correct
4 Correct 99 ms 22476 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 23 ms 4816 KB Output is correct
8 Correct 476 ms 23808 KB Output is correct
9 Correct 498 ms 23800 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 23776 KB Output is correct
2 Correct 163 ms 23556 KB Output is correct
3 Correct 162 ms 23624 KB Output is correct
4 Correct 187 ms 23548 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 3 ms 2848 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 5 ms 2944 KB Output is correct
6 Correct 23 ms 4364 KB Output is correct
7 Correct 541 ms 19328 KB Output is correct
8 Correct 592 ms 23804 KB Output is correct
9 Correct 128 ms 19392 KB Output is correct
10 Correct 334 ms 19064 KB Output is correct
11 Correct 129 ms 21800 KB Output is correct
12 Correct 120 ms 21800 KB Output is correct
13 Correct 162 ms 23628 KB Output is correct