oj.uz

Submission #1041175

# Submission time Handle Problem Language Result Execution time Memory
1041175 2024-08-01T16:58:58 Z TrinhKhanhDung Synchronization (JOI13_synchronization) C++14
100 / 100
 145 ms 23080 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(998244353)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

struct fen{
    vector<int> val;
    int n;

    fen(int _n = 0){
        n = _n;
        val.resize(n + 3, 0);
    }

    void update(int p, int c){
        while(p <= n){
            val[p] += c;
            p += p & -p;
        }
    }

    int getVal(int p){
        int ans = 0;
        while(p > 0){
            ans += val[p];
            p -= p & -p;
        }
        return ans;
    }
} bit;

const int MAX = 1e5 + 10, LOG = 17;

int N, M, Q;
vector<int> adj[MAX];
vector<pair<int, int>> save;
int d[MAX][LOG], in[MAX], out[MAX], timer, sta[MAX], num[MAX];

void dfs(int u, int p){
    d[u][0] = p;
    for(int i=1; i<LOG; i++){
        d[u][i] = d[d[u][i - 1]][i - 1];
    }
    in[u] = ++timer;
    for(int v: adj[u]) if(v != p){
        dfs(v, u);
    }
    out[u] = timer;
}

int root(int u){
    int cur = bit.getVal(in[u]);
    for(int i=LOG-1; i>=0; i--) if(d[u][i] != 0){
        int v = d[u][i];
        if(bit.getVal(in[v]) == cur){
            u = v;
        }
    }
    return u;
}

void solve(){
    cin >> N >> M >> Q;
    for(int i=1; i<N; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        save.push_back(make_pair(u, v));
    }
    dfs(1, 0);
    bit = fen(N);
    for(int i=1; i<=N; i++){
        bit.update(in[i], 1);
        bit.update(out[i] + 1, -1);
    }
    for(int i=1; i<=N; i++){
        num[i] = 1;
    }
    while(M--){
        int id; cin >> id;
        id--;
        int u = save[id].fi, v = save[id].se;
        if(d[u][0] == v){
            swap(u, v);
        }
        if(sta[id] != -1){
            bit.update(in[v], -1);
            bit.update(out[v] + 1, 1);
            int r = root(u);
            num[r] += num[v] - sta[id];
            sta[id] = -1;
        }
        else{
            bit.update(in[v], 1);
            bit.update(out[v] + 1, -1);
            int r = root(u);
            num[v] = sta[id] = num[r];
        }
    }
    while(Q--){
        int u; cin >> u;
        cout << num[root(u)] << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("deggraph.inp", "r", stdin);
//    freopen("deggraph.out", "w", stdout);

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

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6744 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 8 ms 9308 KB Output is correct
8 Correct 6 ms 9300 KB Output is correct
9 Correct 6 ms 9308 KB Output is correct
10 Correct 73 ms 17600 KB Output is correct
11 Correct 77 ms 17492 KB Output is correct
12 Correct 112 ms 22212 KB Output is correct
13 Correct 40 ms 17604 KB Output is correct
14 Correct 48 ms 17092 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 19656 KB Output is correct
2 Correct 53 ms 19652 KB Output is correct
3 Correct 52 ms 21704 KB Output is correct
4 Correct 50 ms 21700 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 10 ms 10000 KB Output is correct
8 Correct 145 ms 22984 KB Output is correct
9 Correct 143 ms 23080 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 22976 KB Output is correct
2 Correct 82 ms 22832 KB Output is correct
3 Correct 78 ms 22720 KB Output is correct
4 Correct 78 ms 22812 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 8 ms 9564 KB Output is correct
7 Correct 99 ms 18372 KB Output is correct
8 Correct 145 ms 22984 KB Output is correct
9 Correct 53 ms 18624 KB Output is correct
10 Correct 63 ms 18368 KB Output is correct
11 Correct 60 ms 20928 KB Output is correct
12 Correct 58 ms 20936 KB Output is correct
13 Correct 77 ms 22832 KB Output is correct