oj.uz

Submission #807148

# Submission time Handle Problem Language Result Execution time Memory
807148 2023-08-04T14:10:59 Z thimote75 Synchronization (JOI13_synchronization) C++14
100 / 100
 393 ms 26820 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);
    }
};

const int MAXK = 20;

struct RootFinder {
    idata parent;
    igrid parents_2k;
    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);

        parents_2k.resize(N, idata(MAXK, -1));
        
        for (int i = 0; i < N; i ++) parents_2k[i][0] = parent[i];

        for (int k = 0; k + 1 < MAXK; k ++) {
            for (int i = 0; i < N; i ++) {
                if (parents_2k[i][k] == -1) continue ;

                parents_2k[i][k + 1] = parents_2k[parents_2k[i][k]][k];
            }
        }
    }

    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 getRoot (int node) {
        if (rooter.query(node, node) == 1) return node;

        int start = node;
        for (int k = MAXK - 1; k >= 0; k --) {
            int pot = parents_2k[node][k];
            if (pot == -1) continue ;

            int res = rooter.query(pot, start);
            if (res != 0) continue ;
            
            node = pot;
        }

        return parent[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 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 14 ms 2608 KB Output is correct
8 Correct 13 ms 2576 KB Output is correct
9 Correct 19 ms 2656 KB Output is correct
10 Correct 176 ms 23200 KB Output is correct
11 Correct 206 ms 23128 KB Output is correct
12 Correct 194 ms 26116 KB Output is correct
13 Correct 117 ms 23640 KB Output is correct
14 Correct 138 ms 23148 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 24832 KB Output is correct
2 Correct 156 ms 24584 KB Output is correct
3 Correct 182 ms 26112 KB Output is correct
4 Correct 161 ms 26192 KB Output is correct

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 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 3 ms 468 KB Output is correct
7 Correct 34 ms 2968 KB Output is correct
8 Correct 353 ms 26392 KB Output is correct
9 Correct 346 ms 26456 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 26392 KB Output is correct
2 Correct 379 ms 26584 KB Output is correct
3 Correct 393 ms 26816 KB Output is correct
4 Correct 377 ms 26724 KB Output is correct

Subtask #5
40.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 3 ms 468 KB Output is correct
6 Correct 30 ms 2644 KB Output is correct
7 Correct 344 ms 23380 KB Output is correct
8 Correct 348 ms 26376 KB Output is correct
9 Correct 240 ms 23952 KB Output is correct
10 Correct 318 ms 23800 KB Output is correct
11 Correct 343 ms 25352 KB Output is correct
12 Correct 343 ms 25416 KB Output is correct
13 Correct 378 ms 26820 KB Output is correct