oj.uz

Submission #639833

# Submission time Handle Problem Language Result Execution time Memory
639833 2022-09-12T07:54:36 Z Micchon Synchronization (JOI13_synchronization) C++14
0 / 100
 415 ms 31844 KB 
#include<bits/stdc++.h>
#define int long long
#define vi vector<int>
#define forn(i,n) for(int i = 0; i < n; ++i)

using namespace std;
const int MOD = 1000000007;

int n,m,q;
vector<vector<int>> adj;
vi val, bef;
vector<bool> isOn;
vector<pair<int,int>> lines;
int fen[1 << 18];
int in[1 << 17], out[1 << 17];
int time_idx;
int sparse[1 << 17][18];

void upd(int pos, int v) {
    // Update fenwick tree
    // Always update the child node
    while(pos < (1 << 18)) {
        fen[pos] += v;
        pos += pos & (-pos);
    }
}

int get_fen(int pos) {
    int v = 0;
    while(pos) {
        v += fen[pos];
        pos -= pos & (-pos);
    } 
    return v;
}

void toggleEdge(int idx) {
    int changeVal = isOn[idx] ? 1 : -1;
    upd(in[lines[idx].second], changeVal);
    upd(out[lines[idx].second], -changeVal);
    isOn[idx] = !isOn[idx];
}

void createTree(int now = 0, int prev = -1) {
    in[now] = time_idx++;
    sparse[now][0] = prev;
    for(int &x: adj[now]) {
        if(x == prev) continue;
        createTree(x, now);
    }
    out[now] = time_idx;
}

void createSparse() {
    for(int b = 0; b < 18; b++) {
        for(int i = 0; i < n; i++) {
            sparse[i][b] = sparse[sparse[i][b-1]][b-1];
        }
    }
}

void turnAllEdgesOn() {
    forn(i, n-1) {
        toggleEdge(i);
    }
}

void sortLinesOrder() {
    forn(i, n-1) {
        if(in[lines[i].first] > in[lines[i].second]) {
            swap(lines[i].first, lines[i].second);
        }
    }
}

int searchParent(int x) {
    int initx = x;
    for(int b = 17; b >= 0; b--) {
        if(sparse[x][b] == -1 || get_fen(in[initx]) != get_fen(in[sparse[x][b]])) {
            continue;
        }
        x = sparse[x][b];
    }
    return x;
}

void solve() {
    cin >> n >> m >> q;
    memset(fen, 0, sizeof(fen));
    lines.resize(n);
    adj.resize(n, vi());
    val.resize(n, 1);
    bef.resize(n, 0);
    isOn.resize(n, 1);

    forn(i, n-1) {
        cin >> lines[i].first >> lines[i].second;
        lines[i].first--;
        lines[i].second--;
        adj[lines[i].first].push_back(lines[i].second);
        adj[lines[i].second].push_back(lines[i].first);
    }
    time_idx = 1;
    createTree();
    sortLinesOrder();
    turnAllEdgesOn();

    forn(i, m) {
        int u;
        cin >> u;
        u--;
        if(isOn[u]) {
            // sekarang disable, nilai val[parent] dicopy ke child (karena child jadi parent baru)
            bef[lines[u].second] = val[searchParent(lines[u].second)];
            val[lines[u].second] = bef[lines[u].second];
        }
        else {
            // sekarang enable, val parent berubah
            int childVal = val[lines[u].second];
            int childBef = bef[lines[u].second];
            //cout << "change val " << searchParent(lines[u].first) << " by " << childVal << "-" << childBef << '\n';
            val[searchParent(lines[u].first)] += childVal - childBef;
        }
        toggleEdge(u);
        //cout << "After " << i+1 << " changes:\n";
        //forn(j, n) {
        //    cout << "  Parent of " << j << " is " << searchParent(j) << " with val = " << val[searchParent(j)] << '\n'; 
        //}
    }

    forn(i, q) {
        int u;
        cin >> u;
        u--;
        //cout << u << "  " << searchParent(u) << '\n';
        cout << val[searchParent(u)] << '\n';
    }


}

int32_t main() 
{
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Correct 1 ms 2260 KB Output is correct
3 Incorrect 1 ms 2260 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 154 ms 31396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 415 ms 31844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Correct 2 ms 2356 KB Output is correct
3 Incorrect 1 ms 2260 KB Output isn't correct
4 Halted 0 ms 0 KB -