제출 #539080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
539080		Jeff12345121	동기화 (JOI13_synchronization)	C++14	100 / 100	1040 ms	38736 KiB

synchronization

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40