oj.uz

Submission #956458

# Submission time Handle Problem Language Result Execution time Memory
956458 2024-04-02T01:44:18 Z vjudge1 Synchronization (JOI13_synchronization) C++17
100 / 100
 280 ms 51340 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 5 ms 15448 KB Output is correct
2 Correct 3 ms 15452 KB Output is correct
3 Correct 3 ms 15552 KB Output is correct
4 Correct 3 ms 15624 KB Output is correct
5 Correct 3 ms 15620 KB Output is correct
6 Correct 5 ms 15704 KB Output is correct
7 Correct 13 ms 19924 KB Output is correct
8 Correct 16 ms 19928 KB Output is correct
9 Correct 13 ms 19928 KB Output is correct
10 Correct 168 ms 44696 KB Output is correct
11 Correct 185 ms 44968 KB Output is correct
12 Correct 223 ms 50660 KB Output is correct
13 Correct 77 ms 44560 KB Output is correct
14 Correct 114 ms 43388 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 46784 KB Output is correct
2 Correct 79 ms 46480 KB Output is correct
3 Correct 101 ms 49244 KB Output is correct
4 Correct 99 ms 49084 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15612 KB Output is correct
2 Correct 3 ms 15452 KB Output is correct
3 Correct 3 ms 15620 KB Output is correct
4 Correct 4 ms 15652 KB Output is correct
5 Correct 3 ms 15704 KB Output is correct
6 Correct 5 ms 15964 KB Output is correct
7 Correct 18 ms 20440 KB Output is correct
8 Correct 253 ms 51132 KB Output is correct
9 Correct 265 ms 51176 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 51340 KB Output is correct
2 Correct 146 ms 50112 KB Output is correct
3 Correct 151 ms 50388 KB Output is correct
4 Correct 145 ms 50204 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 3 ms 15448 KB Output is correct
3 Correct 3 ms 15452 KB Output is correct
4 Correct 3 ms 15612 KB Output is correct
5 Correct 4 ms 15796 KB Output is correct
6 Correct 16 ms 19928 KB Output is correct
7 Correct 202 ms 45624 KB Output is correct
8 Correct 280 ms 51276 KB Output is correct
9 Correct 84 ms 45800 KB Output is correct
10 Correct 146 ms 44784 KB Output is correct
11 Correct 99 ms 48060 KB Output is correct
12 Correct 104 ms 48064 KB Output is correct
13 Correct 150 ms 50220 KB Output is correct