Submission #807141

#	Time	Username	Problem	Language	Result	Execution time	Memory
807141		thimote75	Synchronization (JOI13_synchronization)	C++14	20 / 100	8063 ms	14740 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

template<typename T>
string to_string(T x) {
    string S = "[";
    bool first = true;
    for (const auto v : x) {
        if (!first) S += ", ";
        S += to_string(v); 
        first = false;
    }
    S += "]";
    return S;
}

string to_string(string x) {
    return x;
}

template<typename A, typename B>
string to_string (pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void dbg_out () { cout << endl; }
template<typename Head, typename... Tail>
void dbg_out (Head H, Tail... T) {
    cout << to_string(H) << " ";
    dbg_out(T...);
}

#ifdef DEBUG
#  define dbg(...) cout << "(" << #__VA_ARGS__ << "): ";  dbg_out(__VA_ARGS__);
#else
#  define dbg(...)
#endif

using bdata = vector<bool>;

int N, M, Q;

struct Road {
    int a, b;
    
    bool status = false;
    int next (int node) {
        return a == node ? b : a;
    }
};

vector<Road> road_array;

using idata = vector<int>;
using igrid = vector<idata>;

using graph = igrid;

graph roads;

struct PathSum {
    idata preordre;
    idata postordre;
    int ordre = 0;

    idata tree;

    int start, height;
    void __modify (int node, int value) {
        node += start;

        int delta = value - tree[node];
        while (node != 0) {
            tree[node] += delta;
            node >>= 1;
        }
    }
    void modify (int node, int value) {
        __modify( preordre[node],   value);
        __modify(postordre[node], - value);
    }
    int query (int parent, int node) {
        int left  = start + preordre[parent];
        int right = start + preordre[node];

        int res = 0;
        while (left < right) {
            if ((left  & 1) == 1) res += tree[left];
            if ((right & 1) == 0) res += tree[right];

            left  = (left  + 1) >> 1;
            right = (right - 1) >> 1;
        }

        if (left == right) res += tree[left];
        return res;
    }

    void dfs (int node, int parent) {
        preordre[node] = ordre ++;

        for (int iR : roads[node]) {
            Road &road = road_array[iR];
            int   next = road.next(node);

            if (next == parent) continue ;

            dfs(next, node);
        }

        postordre[node] = ordre ++;
    }
    void init () {
        preordre.resize(N);
        postordre.resize(N);
        dfs(0, -1);

        height = ceil(log2(2 * N));
        start  = 1 << height;
        tree.resize(start << 1);
    }
};

struct RootFinder {
    idata parent;
    idata depth;

    PathSum rooter;

    void dfs (int node, int _parent, int _depth) {
        parent[node] = _parent;
        depth [node] = _depth;

        for (int iRoad : roads[node]) {
            Road &road = road_array[iRoad];
            int   next = road.next(node);

            if (next == _parent) continue ;

            dfs(next, node, _depth + 1);
        }
    }
    void init () {
        parent.resize(N, -1);
        depth .resize(N, -1);

        rooter.init();
        for (int i = 0; i < N; i ++)
            rooter.modify(i, 1);

        dfs(0, -1, 0);
    }

    void setRoot (int node, bool value) {
        rooter.modify(node, value ? 1 : 0);
    }

    int getRoot (int node) {
        int start = node;
        while (rooter.query(node, start) == 0)
            node = parent[node];
        return node;
    }
    int getParent (int node) {
        return parent[node];
    }
    int getDepth (int node) {
        return depth[node];
    }

};

struct TreeDataMaintainer {
    idata delta;
    idata omega;
    int size;

    RootFinder* finder;

    TreeDataMaintainer (int _size, RootFinder* _finder) {
        size   = _size;
        finder = _finder;

        delta .resize(size, 1);
        omega .resize(size, 1);
    }

    void attach (int parent, int node) {
        int root = finder->getRoot(parent);

        omega[root] += delta[node];
        delta[root] += delta[node];

        finder->setRoot(node, false);
    }
    void detach (int parent, int node) {
        int root = finder->getRoot(parent);

        omega[node] = omega[root];
        delta[node] = 0;

        finder->setRoot(node, true);
    }
    int getValue (int node) {
        int root = finder->getRoot(node);

        return omega[root];
    }
};

int main () {
    cin >> N >> M >> Q;

    roads.resize(N);

    for (int i = 1; i < N; i ++) {
        int a, b;
        cin >> a >> b;
        a --; b --;

        Road road;
        road.a = a; road.b = b;
        road_array.push_back(road);

        roads[a].push_back(i - 1);
        roads[b].push_back(i - 1);
    }

    RootFinder finder; finder.init();
    for (int i = 0; i + 1 < N; i ++) {
        Road &road = road_array[i];

        if (finder.getDepth(road.a) > finder.getDepth(road.b))
            swap(road.a, road.b);
    }

    TreeDataMaintainer metadata(N, &finder);

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

        Road &road = road_array[x];

        if (road.status) metadata.detach( road.a, road.b );
        else metadata.attach(road.a, road.b);

        road.status = !road.status;
    }

    for (int q = 0; q < Q; q ++) {
        int x; cin >> x; x --;

        cout << metadata.getValue(x) << "\n";
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 10 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40