oj.uz

Submission #539080

# Submission time Handle Problem Language Result Execution time Memory
539080 2022-03-18T11:14:59 Z Jeff12345121 Synchronization (JOI13_synchronization) C++14
100 / 100
 1040 ms 38736 KB 
#include <bits/stdc++.h>
#define dbg(x) if(COND) {cout << #x << "=" << x << "\n";}
#define dbgp(x) if(COND) {cout << #x << "= {" << x.first << "," << x.second << "}\n";}
#define dbgv(x) if(COND) {cout << #x << ": "; for (auto k : x) { cout << k << " "; } cout << "\n";}
#define dbgvp(x) if(COND) {cout << #x << ":\n"; for (auto k : x) { dbgp(k) } cout << "\n";}
#define dbgm(x) if(COND) {int ind = 0; cout << #x << ":\n"; for (auto k : x) { cout << ind++ << ": "; for (auto p : k) {cout << p << " ";} cout << "\n";} cout << "\n";}
#define dbgmp(x) if(COND) {int ind = 0; cout << #x << ":\n"; for (auto k : x) { cout << ind++ << ": "; for (auto p : k) {cout << "{" << p.first << "," << p.second << "} ";} cout << "\n";} cout << "\n";}
#define dbga(x , n) if(COND) {cout << #x << ": "; for(int i = 1; i <= n; i++) { cout << a[i] << " "; } cout << "\n";}
#define dbga2(x , n , m) if(COND) {cout << #x << ":\n"; for(int i = 1; i <= n; i++) { cout << i << ": "; for (int j = 1; j <= m; j++) {cout << a[i][j] << " ";} cout << "\n"; } cout << "\n";}
#define brk(x) if(x) { COND = true; } else { COND = false; }
#define sep if (COND) {cout << "\n-------------------------------\n\n";}
#define dbgdeq(q) if (COND) {cout << #q << ": "; deque<int> qc = q; while(!qc.empty()) {cout << qc.front() << " "; qc.pop_front();} cout << "\n"; }
#define int long long
using namespace std;

bool COND = true;


#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
#define in cin
#define out cout
#endif // LOCAL

int n,m,q;
const int nmax = 300005;
vector<vector<pair<int,int>>> g;
vector<pair<int,int>> lines;

int nrEuler;

///returns the number of inactive edges from node to root

struct Bit {
    int v[nmax];
    int query(int pos) {
        int s = 0;
        for (; pos > 1; pos -= (pos &(-pos))) {
            s += v[pos];
        }
        return s;
    }
    void update(int pos, int val) {
        for (; pos <= nrEuler; pos += (pos & (-pos))) {
            v[pos] += val;
        }
    }
};
Bit bit;

vector<int> par,first,last,Rank;
///returns the number of inactive nodes from root to node
int inactive(int node) {
    return bit.query(first[node]);
}

void euler(int node, int &ind) {
    first[node] = ++ind;
    for (auto k : g[node]) {
        if (par[node] == k.first) continue;
        par[k.first] = node;
        Rank[k.first] = Rank[node] + 1;
        euler(k.first , ind);
    }
    last[node] = ++ind;
}

///returns the highest node in the component of 'node', which is the first
///node that has less inactive components than node.
const int MAXPUT = 20;
int lift[MAXPUT][nmax];
void getLift() {
    for (int i = 1; i <= n; i++) {
        lift[0][i] = par[i];
    }
    for (int p = 1; (1 << p) <= n; p++) {
        for (int i = 1; i <= n; i++) {
            lift[p][i] = lift[p - 1][lift[p - 1][i]];
        }
    }
    /*
    for (int p = 0; p <= 10; p++) {
        for (int i = 1; i <= n; i++) {
            cout << "p = " << p << " i = " << i << ": " << lift[p][i] << "\n";
        }
        cout << "\n";
    }cout << "\n";*/
}
int root(int node) {
    int nodeInactive = inactive(node);
    int r = node;
    for (int p = MAXPUT - 1; p >= 0; p--) {
        if (lift[p][r] == 0) continue;
        if (inactive(lift[p][r]) == nodeInactive) {
            r = lift[p][r];
        }
    }
    return r;
}
int32_t main() {
    in >> n >> m >> q;
    lines.resize(n);
    g.resize(n + 1);
    par.resize(n + 1);
    first.resize(n + 1);
    last.resize(n + 1);
    Rank.resize(n + 1);
    for (int i = 1; i < n; i++) {
        int u,v;
        in >> u >> v;
        g[u].push_back({v,i});
        g[v].push_back({u,i});
        lines[i] = {u,v};
    }



    nrEuler = 0;
    euler(1 , nrEuler);


    auto deactivate = [&](int u, int v) {
        ///u is parent, v is child
        if (Rank[u] > Rank[v]) swap(u,v);

        bit.update(first[v] , 1);
        bit.update(last[v]  , -1);
    };

    auto activate = [&](int u, int v) {
        if (Rank[u] > Rank[v]) swap(u,v);

        bit.update(first[v] , -1);
        bit.update(last[v]  , 1);
    };

    for (int i = 1; i < n; i++) {
        deactivate(lines[i].first , lines[i].second);
    }

    getLift();

    vector<int> sol(n + 1 , 1);
    vector<int> status(n , 0); /// 0 = inactive, 1 = active
    vector<int> lastAdded(n , 0); /// 0 = inactive, 1 = active
    for (int i = 1; i <= m; i++) {
        int ind;
        in >> ind;
        int u = lines[ind].first;
        int v = lines[ind].second;



        ///u is parent, v is child
        if (Rank[u] > Rank[v]) swap(u,v);
        if (status[ind] == 0) { /// its currently inactive
            int r = root(u);
            sol[r] += sol[v] - lastAdded[ind];
          //  lastAdded[ind] = sol[v];
            activate(u , v);
            status[ind] = 1;
        } else {
            sol[v] = sol[root(u)];
            lastAdded[ind] = sol[v];
            deactivate(u,v);
            status[ind] = 0;
        }
    }

    for (int i = 1; i <= q; i++) {
        int x;
        in >> x;
        out << sol[root(x)] << "\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 20 ms 3272 KB Output is correct
8 Correct 23 ms 3284 KB Output is correct
9 Correct 21 ms 3284 KB Output is correct
10 Correct 420 ms 32140 KB Output is correct
11 Correct 453 ms 32148 KB Output is correct
12 Correct 750 ms 37868 KB Output is correct
13 Correct 210 ms 31316 KB Output is correct
14 Correct 288 ms 31512 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 32452 KB Output is correct
2 Correct 162 ms 34124 KB Output is correct
3 Correct 203 ms 37396 KB Output is correct
4 Correct 230 ms 37304 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 49 ms 3980 KB Output is correct
8 Correct 1012 ms 38720 KB Output is correct
9 Correct 1040 ms 38728 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 972 ms 35900 KB Output is correct
2 Correct 380 ms 38432 KB Output is correct
3 Correct 387 ms 38464 KB Output is correct
4 Correct 394 ms 38576 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 39 ms 3388 KB Output is correct
7 Correct 563 ms 33048 KB Output is correct
8 Correct 804 ms 38736 KB Output is correct
9 Correct 330 ms 32472 KB Output is correct
10 Correct 418 ms 32780 KB Output is correct
11 Correct 306 ms 35632 KB Output is correct
12 Correct 311 ms 35788 KB Output is correct
13 Correct 352 ms 38576 KB Output is correct