oj.uz

Submission #597532

# Submission time Handle Problem Language Result Execution time Memory
597532 2022-07-16T08:59:51 Z AA_Surely Synchronization (JOI13_synchronization) C++17
50 / 100
 157 ms 24052 KB 
#include <bits/stdc++.h>

#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)

#define WTF cout << "WTF" << endl

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define pb push_back

#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;

const int N = 4e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;

#define lc now << 1
#define rc now << 1 | 1
#define endl '\n'

int n, m, q, t[N], cnt;
int par[N], ans[N], mem[N], sz[N], head[N], order[N];
bool exist[N];
PII eset[N];
VPII adj[N];

struct SegTree {
    int seg[N << 2];

    void change(int id, int val, int now = 1, int ls = 0, int rs = n - 1) {
        if (ls == rs) {
            seg[now] = val;
            return;
        }

        int mid = (ls + rs) >> 1;
        if (id <= mid) change(id, val, lc, ls, mid);
        else change(id, val, rc, mid + 1, rs);

        seg[now] = seg[lc] + seg[rc];
        return;
    }

    int rightest(int rq, int now = 1, int ls = 0, int rs = n - 1) {
        if (ls > rq || seg[now] == (rs - ls + 1)) return -1;
        if (ls == rs) return ls;

        int mid = (ls + rs) >> 1;
        int case1 =  rightest(rq, rc, mid + 1, rs);
        return (case1 != -1 ? case1 : rightest(rq, lc, ls, mid));
    }
} tree;

void init() {
    cin >> n >> m >> q;
    F0R(i, n - 1) {
        int u, v; cin >> u >> v;
        adj[--u].pb({--v, i});
        adj[v].pb({u, i});
        eset[i] = {u, v};
    }

    return;
}

void preD(int now, int p) {
    order[cnt] = now;
    t[now] = cnt++;
    sz[now] = 1;
    par[now] = p;

    for(const auto &[on, id] : adj[now]) if (on != p) {
        preD(on, now);
        sz[now] += sz[on];
    }

    return;
}

void dfs(int now) {
    if (!now) head[ adj[now][0].F ] = head[now];
    else if (adj[now].size() >= 2) head[ adj[now][1].F ] = head[now];
    for(const auto &[on, id] : adj[now]) if (on != par[now]) {
        if (on == eset[id].F) swap(eset[id].F, eset[id].S);
        dfs(on);
    }
}

void rebuild() {
    preD(0, -1);
    F0R(i, n) sort(ALL(adj[i]), [](const PII &a, const PII &b){return sz[a.F] > sz[b.F];});
    iota(head, head + n, 0);
    dfs(0);

    /*F0R(i, n) {
        cout << i + 1 << " : ";
        for(const auto &[on, id] : adj[i]) cout << on + 1 << ' '; cout << endl;
    }*/

    fill(ans, ans + n, 1);

    return;
}

int grand(int v) {
    int pl = tree.rightest(t[v]);
    if (pl < t[ head[v] ]) return grand(par[ head[v] ]);
    return order[pl];
}

inline int get(int v) {
    return ans[ grand(v) ];
}

void rem(int x) {
    mem[x] = get(eset[x].F);
    tree.change(t[ eset[x].S ], 0);
    ans[ eset[x].S ] = mem[x];
    exist[x] = 0;
    return;
}

void add(int x) {
    int up = get(eset[x].F);
    int dn = ans[ eset[x].S ];

    int p = grand(eset[x].F);
    ans[p] = up + dn - mem[x];
    tree.change(t[ eset[x].S ], 1);

    exist[x] = 1;
    return;
}

int main() {
    IOS;

    init();
    rebuild();
    
    while(m--) {
        int id; cin >> id; id--;
        if (exist[id]) rem(id);
        else add(id);
    }

    while(q--) {
        int v; cin >> v; v--;
        cout << get(v) << '\n';
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Incorrect 5 ms 9684 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 20732 KB Output is correct
2 Correct 76 ms 20556 KB Output is correct
3 Correct 62 ms 23408 KB Output is correct
4 Correct 66 ms 23404 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 17 ms 11224 KB Output is correct
8 Correct 139 ms 23924 KB Output is correct
9 Correct 143 ms 23928 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 24012 KB Output is correct
2 Correct 84 ms 23968 KB Output is correct
3 Correct 87 ms 24052 KB Output is correct
4 Correct 83 ms 24012 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9780 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Incorrect 7 ms 9684 KB Output isn't correct
5 Halted 0 ms 0 KB -