oj.uz

Submission #1104155

# Submission time Handle Problem Language Result Execution time Memory
1104155 2024-10-23T03:40:21 Z InvMOD Synchronization (JOI13_synchronization) C++14
100 / 100
 222 ms 26960 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+5;
const int lg = 21;

int n, m, q, timerDFS, tin[N], tout[N], h[N], par[lg][N], bit[N<<1], info[N], last_sync[N];
pair<int,int> E[N];
bool on[N];

vector<int> adj[N];

void update(int p, int val){
    for(; p <= timerDFS; p += (p & (-p))) bit[p] += val;
}

int get(int p){
    int res = 0;
    for(; p; p -= (p & (-p))) res += bit[p];
    return res;
}

void dfs(int x, int p){
    tin[x] = ++timerDFS;
    info[x] = 1;

    for(int v : adj[x])if(v != p){

        h[v] = h[x] + 1;
        par[0][v] = x;
        for(int i = 1; i < lg; i++) par[i][v] = par[i-1][par[i-1][v]];

        dfs(v, x);
    }

    tout[x] = ++timerDFS;
    return;
}

int get_par(int x){
    int cur_node = x, state = get(tin[x]);

    for(int i = lg-1; i >= 0; i--){
        if(par[i][cur_node] && get(tin[par[i][cur_node]]) == state) cur_node = par[i][cur_node];
    }

    return cur_node;
}

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);
        E[i] = make_pair(u, v);
    }

    dfs(1, -1);

    for(int i = 1; i <= n; i++){
        update(tin[i], -1);
        update(tout[i], 1);
    }

    while(m--){
        int d; cin >> d;
        int u = E[d].first, v = E[d].second;

        if(h[u] > h[v]) swap(u, v);


        int asc = get_par(u);

        if(!on[d]){
            info[asc] = info[asc] + (info[v] - last_sync[v]);
            //cout << asc << " " << info[asc] <<"\n";
            update(tin[v], 1);
            update(tout[v], -1);
        }
        else{
            info[v] = info[asc];
            last_sync[v] = info[asc];
            update(tin[v], -1);
            update(tout[v], 1);
        }

        on[d] = on[d] ^ 1;
    }

    while(q--){
        int u; cin >> u;
        cout << info[get_par(u)] <<"\n";
    }
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message

synchronization.cpp: In function 'int32_t main()':
synchronization.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12880 KB Output is correct
2 Correct 2 ms 12880 KB Output is correct
3 Correct 2 ms 12880 KB Output is correct
4 Correct 3 ms 12880 KB Output is correct
5 Correct 2 ms 12960 KB Output is correct
6 Correct 3 ms 12880 KB Output is correct
7 Correct 12 ms 13392 KB Output is correct
8 Correct 10 ms 13392 KB Output is correct
9 Correct 10 ms 13564 KB Output is correct
10 Correct 105 ms 17832 KB Output is correct
11 Correct 132 ms 20164 KB Output is correct
12 Correct 189 ms 26184 KB Output is correct
13 Correct 56 ms 19836 KB Output is correct
14 Correct 88 ms 19528 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 21072 KB Output is correct
2 Correct 71 ms 22800 KB Output is correct
3 Correct 75 ms 25628 KB Output is correct
4 Correct 78 ms 25680 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12880 KB Output is correct
2 Correct 2 ms 12880 KB Output is correct
3 Correct 3 ms 12880 KB Output is correct
4 Correct 3 ms 12880 KB Output is correct
5 Correct 3 ms 13048 KB Output is correct
6 Correct 3 ms 12880 KB Output is correct
7 Correct 15 ms 13904 KB Output is correct
8 Correct 196 ms 25672 KB Output is correct
9 Correct 214 ms 26956 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 24136 KB Output is correct
2 Correct 116 ms 26636 KB Output is correct
3 Correct 120 ms 26696 KB Output is correct
4 Correct 119 ms 26704 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12880 KB Output is correct
2 Correct 3 ms 12880 KB Output is correct
3 Correct 3 ms 12880 KB Output is correct
4 Correct 3 ms 12880 KB Output is correct
5 Correct 3 ms 12880 KB Output is correct
6 Correct 12 ms 13392 KB Output is correct
7 Correct 136 ms 18112 KB Output is correct
8 Correct 214 ms 26960 KB Output is correct
9 Correct 71 ms 20972 KB Output is correct
10 Correct 119 ms 20812 KB Output is correct
11 Correct 84 ms 24144 KB Output is correct
12 Correct 86 ms 24136 KB Output is correct
13 Correct 110 ms 26708 KB Output is correct