oj.uz

Submission #597613

# Submission time Handle Problem Language Result Execution time Memory
597613 2022-07-16T11:50:01 Z AA_Surely Synchronization (JOI13_synchronization) C++17
100 / 100
 211 ms 22188 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 = 2e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;

#define lc now << 1
#define rc now << 1 | 1

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];

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 g(int id, int now = 1, int ls = 0, int rs = n - 1) {
    if (ls == rs) return seg[now];
    int mid = (ls + rs) >> 1;
    if (id <= mid) return g(id, lc, ls, mid);
    else return g(id, rc, mid + 1, rs);
}

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));
}

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) {
    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) {
    order[cnt] = now;
    t[now] = cnt++;
    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, n);
    adj[0].pb({n, m});
    sz[n] = n + 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);

    fill(ans, ans + n, 1);

    return;
}

int grand(int v) {
    int pl = 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);
    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 = get(eset[x].S);

    int p = grand(eset[x].F);
    ans[p] = up + dn - mem[x];
    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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5104 KB Output is correct
7 Correct 15 ms 6136 KB Output is correct
8 Correct 15 ms 6100 KB Output is correct
9 Correct 17 ms 6132 KB Output is correct
10 Correct 203 ms 15732 KB Output is correct
11 Correct 164 ms 15744 KB Output is correct
12 Correct 176 ms 21376 KB Output is correct
13 Correct 124 ms 15532 KB Output is correct
14 Correct 117 ms 14784 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 16092 KB Output is correct
2 Correct 114 ms 15856 KB Output is correct
3 Correct 80 ms 18684 KB Output is correct
4 Correct 73 ms 18664 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5204 KB Output is correct
7 Correct 16 ms 6420 KB Output is correct
8 Correct 184 ms 19208 KB Output is correct
9 Correct 152 ms 19340 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 19276 KB Output is correct
2 Correct 102 ms 19300 KB Output is correct
3 Correct 99 ms 19300 KB Output is correct
4 Correct 96 ms 19276 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5172 KB Output is correct
6 Correct 18 ms 6180 KB Output is correct
7 Correct 211 ms 16496 KB Output is correct
8 Correct 198 ms 22188 KB Output is correct
9 Correct 160 ms 16568 KB Output is correct
10 Correct 205 ms 15968 KB Output is correct
11 Correct 129 ms 19272 KB Output is correct
12 Correct 156 ms 19244 KB Output is correct
13 Correct 107 ms 21652 KB Output is correct