oj.uz

Submission #956459

# Submission time Handle Problem Language Result Execution time Memory
956459 2024-04-02T01:45:11 Z Whisper Synchronization (JOI13_synchronization) C++17
100 / 100
 280 ms 48548 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }

const int MAX = 3e5 + 5, N = 3e5;
int numNode, numOperation, numQuery;
vector<int> G[MAX];
vector<pair<int, int>> edge;

int F[MAX];

int tin[MAX], tout[MAX], dep[MAX], up[MAX][21], cnt = 0;
//using fenwick to save the value of node u
//-> all computer in the same component have the same value

void dfs(int u, int p = -1){
    tin[u] = ++cnt;
    for (int&v : G[u]) if(v ^ p){
        dep[v] = dep[u] + 1;
        up[v][0] = u;
        for (int i = 1; i <= 20; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
        dfs(v, u);
    }
    tout[u] = cnt;
}

void modify(int p, int val){
    for (; p <= N; p += p & (-p)) F[p] += val;
}
int query(int p){
    int res = 0;
    for (; p > 0; p -= p & (-p)) res += F[p];
    return res;
}
//get the represent node of the set that contain u
int get_root(int u){
    int ans = u;
    for (int i = 20; i >= 0; --i) if(up[ans][i] && query(tin[u]) == query(tin[up[ans][i]])){
        ans = up[ans][i];
    }
    return ans;
}
bool on[MAX];
int lst_on[MAX], ans[MAX];
void Whisper(){
    cin >> numNode >> numOperation >> numQuery;
    for (int i = 1; i < numNode; ++i){
        int u, v; cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
        edge.emplace_back(u, v);
    }
    dfs(1);
    //pre compute query
    for (int i = 1; i <= numNode; ++i){
        ans[i] = 1;
        if (i > 1) {
            modify(tin[i], 1);
            modify(tout[i] + 1, -1);
        }
    }
    for (int i = 1; i <= numOperation; ++i){
        int id; cin >> id; --id;
        int u = edge[id].first, v = edge[id].second;
        if (dep[u] > dep[v]) swap(u, v);
        if (!on[id]){
            int root = get_root(u);
            ans[root] += ans[v] - lst_on[v];
            modify(tin[v], -1); modify(tout[v] + 1, 1);
        }
        else{
            ans[v] = lst_on[v] = ans[get_root(u)];
            modify(tin[v], 1); modify(tout[v] + 1, -1);
        }
        on[id] ^= 1;
    }

    for (int i = 1; i <= numQuery; ++i){
        int x; cin >> x;
        cout << ans[get_root(x)] << '\n';
    }
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15448 KB Output is correct
2 Correct 3 ms 15448 KB Output is correct
3 Correct 3 ms 15452 KB Output is correct
4 Correct 3 ms 15548 KB Output is correct
5 Correct 3 ms 15452 KB Output is correct
6 Correct 4 ms 15960 KB Output is correct
7 Correct 13 ms 19772 KB Output is correct
8 Correct 12 ms 19672 KB Output is correct
9 Correct 16 ms 19928 KB Output is correct
10 Correct 155 ms 42496 KB Output is correct
11 Correct 155 ms 42564 KB Output is correct
12 Correct 219 ms 48064 KB Output is correct
13 Correct 68 ms 42808 KB Output is correct
14 Correct 115 ms 41668 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 44772 KB Output is correct
2 Correct 79 ms 44488 KB Output is correct
3 Correct 101 ms 47548 KB Output is correct
4 Correct 98 ms 47324 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15452 KB Output is correct
2 Correct 3 ms 15452 KB Output is correct
3 Correct 3 ms 15452 KB Output is correct
4 Correct 3 ms 15708 KB Output is correct
5 Correct 3 ms 15452 KB Output is correct
6 Correct 4 ms 15708 KB Output is correct
7 Correct 18 ms 20208 KB Output is correct
8 Correct 280 ms 48548 KB Output is correct
9 Correct 247 ms 48292 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 48248 KB Output is correct
2 Correct 145 ms 48036 KB Output is correct
3 Correct 142 ms 48060 KB Output is correct
4 Correct 140 ms 48060 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15452 KB Output is correct
2 Correct 4 ms 15640 KB Output is correct
3 Correct 3 ms 15452 KB Output is correct
4 Correct 3 ms 15452 KB Output is correct
5 Correct 5 ms 15704 KB Output is correct
6 Correct 16 ms 19668 KB Output is correct
7 Correct 195 ms 42688 KB Output is correct
8 Correct 269 ms 48412 KB Output is correct
9 Correct 94 ms 43188 KB Output is correct
10 Correct 157 ms 42432 KB Output is correct
11 Correct 107 ms 45660 KB Output is correct
12 Correct 100 ms 45360 KB Output is correct
13 Correct 142 ms 48064 KB Output is correct