Submission #807130

#	Time	Username	Problem	Language	Result	Execution time	Memory
807130		thimote75	Synchronization (JOI13_synchronization)	C++14	40 / 100	8087 ms	12016 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 RootFinder {
    idata parent;
    idata depth;
    bdata isRoot;

    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);

        isRoot.resize(N, true);

        dfs(0, -1, 0);
    }

    void setRoot (int node, bool value) {
        isRoot[node] = value;
    }

    int getRoot (int node) {
        while (!isRoot[node])
            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: 20 / 20
• Subtask 5: 0 / 40