oj.uz

Submission #749890

# Submission time Handle Problem Language Result Execution time Memory
749890 2023-05-28T20:33:32 Z jaredgrxss Synchronization (JOI13_synchronization) C++14
100 / 100
 251 ms 24312 KB 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
using namespace std;


int N, M, Q;
int timer = 1;
int anc[100005][20];
int tin[100005], tout[100005];
vector<int> g[100005];
int bit[100005], info[100005], last_sync[100005];
bool active[100005];
pair<int,int> edges[2*100005];

void dfs(int node = 1, int p = 0) {
    anc[node][0] = p;
    for (int i = 1; i < 20 && anc[node][i-1]; i++) {
        anc[node][i] = anc[anc[node][i-1]][i-1];
    }

    info[node] = 1;
    tin[node] = timer++;
    for (int u : g[node]){
        if (u != p)
            dfs(u, node);
    }
    tout[node] = timer;
}

void add(int i, int v) {
    for (; i <= N; i += (i & (-i))) bit[i] += v;
}

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

int find_anc(int node) {
    int lca = node;
    for (int i = 19; ~i; i--) {
        if (anc[lca][i] && get(tin[anc[lca][i]]) == get(tin[node]))
            lca = anc[lca][i];
    }
    return lca;
}


void solve(){ 
    cin >> N >> M >> Q;

    for (int i = 1; i < N; i++) {
        int v, u; cin >> v >> u;
        edges[i].first = v;
        edges[i].second = u;
        g[v].push_back(u);
        g[u].push_back(v);
    }

    dfs();
    for (int i = 1; i < N+1; i++) {
        add(tin[i], -1);
        add(tout[i], 1);
    }


    for (int i = 0; i < M; i++) {
        int line; cin >> line;

        int u = edges[line].first, v = edges[line].second;

        if (anc[u][0] == v) swap(u,v);

        if (active[line]) {
            info[v] = last_sync[v] = info[find_anc(u)];
            add(tin[v], -1);
            add(tout[v], 1);
        } else {
            info[find_anc(u)] += info[v] - last_sync[v];
            add(tin[v], 1);
            add(tout[v], -1);
        }

        active[line] = !active[line];
    }

    for (int i = 0; i < Q; i++) {
        int node; cin >> node;
        cout << info[find_anc(node)] << '\n';
    }

}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;  
    while(t--) solve();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2760 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 3 ms 2836 KB Output is correct
7 Correct 13 ms 4180 KB Output is correct
8 Correct 10 ms 4180 KB Output is correct
9 Correct 11 ms 4268 KB Output is correct
10 Correct 151 ms 18920 KB Output is correct
11 Correct 160 ms 18812 KB Output is correct
12 Correct 202 ms 23404 KB Output is correct
13 Correct 68 ms 18788 KB Output is correct
14 Correct 113 ms 17792 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 18684 KB Output is correct
2 Correct 77 ms 20512 KB Output is correct
3 Correct 90 ms 22452 KB Output is correct
4 Correct 91 ms 22448 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2692 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2692 KB Output is correct
5 Correct 2 ms 2696 KB Output is correct
6 Correct 3 ms 2836 KB Output is correct
7 Correct 17 ms 4800 KB Output is correct
8 Correct 249 ms 24312 KB Output is correct
9 Correct 250 ms 24220 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 24256 KB Output is correct
2 Correct 149 ms 23620 KB Output is correct
3 Correct 148 ms 23700 KB Output is correct
4 Correct 147 ms 23628 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2696 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 15 ms 4348 KB Output is correct
7 Correct 190 ms 19708 KB Output is correct
8 Correct 251 ms 24140 KB Output is correct
9 Correct 85 ms 19824 KB Output is correct
10 Correct 124 ms 19092 KB Output is correct
11 Correct 103 ms 21852 KB Output is correct
12 Correct 101 ms 21876 KB Output is correct
13 Correct 152 ms 23720 KB Output is correct