oj.uz

Submission #807130

# Submission time Handle Problem Language Result Execution time Memory
807130 2023-08-04T13:49:48 Z thimote75 Synchronization (JOI13_synchronization) C++14
40 / 100
 8000 ms 12016 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 9 ms 1160 KB Output is correct
8 Correct 9 ms 1128 KB Output is correct
9 Correct 9 ms 1108 KB Output is correct
10 Correct 116 ms 8576 KB Output is correct
11 Correct 98 ms 8528 KB Output is correct
12 Correct 96 ms 11300 KB Output is correct
13 Correct 79 ms 8924 KB Output is correct
14 Correct 81 ms 8704 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8058 ms 10052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 21 ms 1436 KB Output is correct
8 Correct 262 ms 11520 KB Output is correct
9 Correct 220 ms 11428 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 11464 KB Output is correct
2 Correct 5838 ms 11744 KB Output is correct
3 Correct 5973 ms 11812 KB Output is correct
4 Correct 5926 ms 12016 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 22 ms 1108 KB Output is correct
7 Correct 239 ms 8832 KB Output is correct
8 Correct 253 ms 11552 KB Output is correct
9 Correct 205 ms 9432 KB Output is correct
10 Correct 225 ms 9348 KB Output is correct
11 Execution timed out 8087 ms 10096 KB Time limit exceeded
12 Halted 0 ms 0 KB -