oj.uz

Submission #881841

# Submission time Handle Problem Language Result Execution time Memory
881841 2023-12-02T03:47:55 Z noompty Synchronization (JOI13_synchronization) C++17
100 / 100
 1267 ms 38172 KB 
#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#include <array>
#include <random>
#include <string>
#include <cassert>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
 
#define ll long long
#define f first
#define s second
 
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
 
template<typename A> void __print(const A &x);
template<typename A, typename B> void __print(const pair<A, B> &p);
template<typename... A> void __print(const tuple<A...> &t);
template<typename T> void __print(stack<T> s);
template<typename T> void __print(queue<T> q);
template<typename T, typename... U> void __print(priority_queue<T, U...> q);
 
template<typename A> void __print(const A &x) {
    bool first = true;
    cerr << '{';
    for (const auto &i : x) {
        cerr << (first ? "" : ","), __print(i);
        first = false;
    }
    cerr << '}';
}
 
template<typename A, typename B> void __print(const pair<A, B> &p) {
    cerr << '(';
    __print(p.f);
    cerr << ',';
    __print(p.s);
    cerr << ')';
}
 
template<typename... A> void __print(const tuple<A...> &t) {
    bool first = true;
    cerr << '(';
    apply([&first] (const auto &...args) { ((cerr << (first ? "" : ","), __print(args), first = false), ...); }, t);
    cerr << ')';
}
 
template<typename T> void __print(stack<T> s) {
    vector<T> debugVector;
    while (!s.empty()) {
        T t = s.top();
        debugVector.push_back(t);
        s.pop();
    }
    reverse(debugVector.begin(), debugVector.end());
    __print(debugVector);
}
 
template<typename T> void __print(queue<T> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.front();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
template<typename T, typename... U> void __print(priority_queue<T, U...> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.top();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
void _print() { cerr << "]\n"; }
 
template <typename Head, typename... Tail> void _print(const Head &H, const Tail &...T) {
    __print(H);
    if (sizeof...(T)) cerr << ", ";
    _print(T...);
}
 
#ifdef DEBUG
	#define D(...) cerr << "Line: " << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__)
#else
	#define D(...)
#endif

struct Node {
    int l, r, s;
    Node *lft, *rht;
    Node (int tl, int tr): l(tl), r(tr), s(0) {
        if (l + 1 != r) {
            lft = new Node(l, (l + r) / 2);
            rht = new Node((l + r) / 2, r);
        } else {
            lft = rht = NULL;
        }
    }
};

void update(Node *x, int pos, int val) {
    if (pos < x->l || x->r <= pos) {
        return;
    }
    if (x->l + 1 == x->r) {
        x->s += val;
        return;
    }
    update(x->lft, pos, val);
    update(x->rht, pos, val);
    x->s = x->lft->s + x->rht->s;
}

int query(Node *x, int l, int r) {
    if (r <= x->l || x->r <= l) {
        return 0;
    }
    if (l <= x->l && x->r <= r) {
        return x->s;
    }
    return query(x->lft, l, r) + query(x->rht, l, r);
}

int n, m, q, depth[100005], sz[100005], par[100005][20], chainTop[100005], chain[100005], chainId, pos[100005], idx, x, u, v, info[100005], linfo[100005];
vector<int> adj[100005];
vector<pair<int, int>> edges;
bool on[100005];
Node *root;

void dfs(int curr, int p) {
    sz[curr] = 1;
    for (int i : adj[curr]) {
        if (i == p) continue;
        depth[i] = depth[curr] + 1;
        par[i][0] = curr;
        dfs(i, curr);
        sz[curr] += sz[i];
    }
}

void hld(int curr, int p) {
    int heavyChild = -1, heavySz = 0;
    chain[curr] = chainId;
    pos[curr] = idx++;
    for (int i : adj[curr]) {
        if (i == p) continue;
        if (sz[i] > heavySz) {
            heavySz = sz[i];
            heavyChild = i;
        }
    }
    if (heavyChild != -1) hld(heavyChild, curr);
    for (int i : adj[curr]) {
        if (i == p || i == heavyChild) continue;
        chainId++;
        chainTop[chainId] = i;
        hld(i, curr);
    }
}

int calc(int st, int en) {
    int curr = st, ret = 0;
    while (chain[curr] != chain[en]) {
        ret += query(root, pos[chainTop[chain[curr]]], pos[curr] + 1);
        curr = par[chainTop[chain[curr]]][0];
    }
    ret += query(root, pos[en] + 1, pos[curr] + 1);
    return ret;
}

int find(int curr) {
    int ret = curr;
    for (int i = 19; i >= 0; i--) {
        if (par[ret][i] && calc(curr, par[ret][i]) == depth[curr] - depth[par[ret][i]]) {
            ret = par[ret][i];
        }
    }
    return ret;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> q;
    edges.push_back({0, 0});
    for (int i = 0, a, b; i < n - 1; i++) {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        edges.push_back({a, b});
    }

    dfs(1, -1);

    for (int i = 1; i < 20; i++) {
        for (int j = 1; j <= n; j++) {
            par[j][i] = par[par[j][i - 1]][i - 1];
        }
    }

    chainTop[0] = 1;
    hld(1, -1);
    root = new Node(0, 100005);

    fill(info, info + 100005, 1);

    while (m--) {
        cin >> x;
        u = edges[x].f, v = edges[x].s;
        if (depth[u] > depth[v]) swap(u, v);
        if (on[x]) {
            info[v] = linfo[v] = info[find(u)];
            update(root, pos[v], -1);
        } else {
            info[find(u)] += info[v] - linfo[v];
            update(root, pos[v], 1);
        }
        on[x] ^= 1;
    }

    while (q--) {
        cin >> x;
        cout << info[find(x)] << "\n";
    }

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18012 KB Output is correct
2 Correct 8 ms 18012 KB Output is correct
3 Correct 10 ms 18012 KB Output is correct
4 Correct 9 ms 18012 KB Output is correct
5 Correct 9 ms 18012 KB Output is correct
6 Correct 10 ms 18012 KB Output is correct
7 Correct 41 ms 18780 KB Output is correct
8 Correct 39 ms 18780 KB Output is correct
9 Correct 41 ms 18780 KB Output is correct
10 Correct 535 ms 29124 KB Output is correct
11 Correct 535 ms 29048 KB Output is correct
12 Correct 978 ms 36896 KB Output is correct
13 Correct 128 ms 29080 KB Output is correct
14 Correct 311 ms 28360 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 32752 KB Output is correct
2 Correct 244 ms 32844 KB Output is correct
3 Correct 340 ms 36300 KB Output is correct
4 Correct 342 ms 36248 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18008 KB Output is correct
2 Correct 8 ms 18012 KB Output is correct
3 Correct 8 ms 18088 KB Output is correct
4 Correct 8 ms 18012 KB Output is correct
5 Correct 8 ms 18144 KB Output is correct
6 Correct 13 ms 18288 KB Output is correct
7 Correct 84 ms 19616 KB Output is correct
8 Correct 1267 ms 37812 KB Output is correct
9 Correct 1231 ms 37644 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1245 ms 38172 KB Output is correct
2 Correct 624 ms 37372 KB Output is correct
3 Correct 623 ms 37340 KB Output is correct
4 Correct 635 ms 37416 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18012 KB Output is correct
2 Correct 8 ms 18012 KB Output is correct
3 Correct 8 ms 18008 KB Output is correct
4 Correct 8 ms 18012 KB Output is correct
5 Correct 11 ms 18160 KB Output is correct
6 Correct 69 ms 18828 KB Output is correct
7 Correct 776 ms 29816 KB Output is correct
8 Correct 1245 ms 37540 KB Output is correct
9 Correct 139 ms 30148 KB Output is correct
10 Correct 489 ms 29896 KB Output is correct
11 Correct 351 ms 33984 KB Output is correct
12 Correct 351 ms 33992 KB Output is correct
13 Correct 637 ms 37392 KB Output is correct