oj.uz

Submission #1077358

# Submission time Handle Problem Language Result Execution time Memory
1077358 2024-08-27T05:49:47 Z mnbvcxz123 Synchronization (JOI13_synchronization) C++17
100 / 100
 273 ms 45760 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(){
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
}
 
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;
 
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;
}

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);
    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;
    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 9308 KB Output is correct
2 Correct 2 ms 9396 KB Output is correct
3 Correct 2 ms 9308 KB Output is correct
4 Correct 2 ms 9480 KB Output is correct
5 Correct 4 ms 7404 KB Output is correct
6 Correct 6 ms 9820 KB Output is correct
7 Correct 13 ms 12228 KB Output is correct
8 Correct 13 ms 16088 KB Output is correct
9 Correct 12 ms 12248 KB Output is correct
10 Correct 136 ms 37816 KB Output is correct
11 Correct 135 ms 39164 KB Output is correct
12 Correct 220 ms 43452 KB Output is correct
13 Correct 89 ms 38916 KB Output is correct
14 Correct 97 ms 34868 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 39924 KB Output is correct
2 Correct 81 ms 37828 KB Output is correct
3 Correct 100 ms 42432 KB Output is correct
4 Correct 100 ms 40636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15616 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 2 ms 9564 KB Output is correct
5 Correct 3 ms 15448 KB Output is correct
6 Correct 5 ms 9820 KB Output is correct
7 Correct 18 ms 18648 KB Output is correct
8 Correct 273 ms 45620 KB Output is correct
9 Correct 257 ms 45760 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 45756 KB Output is correct
2 Correct 145 ms 43204 KB Output is correct
3 Correct 129 ms 44860 KB Output is correct
4 Correct 136 ms 41916 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 15452 KB Output is correct
5 Correct 5 ms 7772 KB Output is correct
6 Correct 16 ms 10452 KB Output is correct
7 Correct 163 ms 40164 KB Output is correct
8 Correct 247 ms 45516 KB Output is correct
9 Correct 81 ms 39864 KB Output is correct
10 Correct 122 ms 39056 KB Output is correct
11 Correct 121 ms 40896 KB Output is correct
12 Correct 100 ms 42248 KB Output is correct
13 Correct 160 ms 43124 KB Output is correct