oj.uz

Submission #807141

# Submission time Handle Problem Language Result Execution time Memory
807141 2023-08-04T14:03:58 Z thimote75 Synchronization (JOI13_synchronization) C++14
20 / 100
 8000 ms 14740 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 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.0 / 10.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 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 11 ms 1428 KB Output is correct
8 Correct 11 ms 1492 KB Output is correct
9 Correct 11 ms 1492 KB Output is correct
10 Correct 145 ms 11456 KB Output is correct
11 Correct 154 ms 11436 KB Output is correct
12 Correct 135 ms 14480 KB Output is correct
13 Correct 95 ms 11752 KB Output is correct
14 Correct 113 ms 11456 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8019 ms 13020 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 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 1 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 23 ms 1812 KB Output is correct
8 Correct 237 ms 14648 KB Output is correct
9 Correct 260 ms 14740 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 14624 KB Output is correct
2 Execution timed out 8041 ms 14356 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.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 280 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 24 ms 1536 KB Output is correct
7 Correct 263 ms 11752 KB Output is correct
8 Correct 248 ms 14608 KB Output is correct
9 Correct 235 ms 12216 KB Output is correct
10 Correct 447 ms 12096 KB Output is correct
11 Execution timed out 8063 ms 12980 KB Time limit exceeded
12 Halted 0 ms 0 KB -