oj.uz

Submission #597611

# Submission time Handle Problem Language Result Execution time Memory
597611 2022-07-16T11:39:26 Z AA_Surely Synchronization (JOI13_synchronization) C++17
50 / 100
 199 ms 19368 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 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) {
    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 (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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 4 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 Incorrect 3 ms 5076 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 94 ms 15988 KB Output is correct
2 Correct 102 ms 15936 KB Output is correct
3 Correct 87 ms 18700 KB Output is correct
4 Correct 95 ms 18668 KB Output is correct

Subtask #3
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 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 15 ms 6496 KB Output is correct
8 Correct 196 ms 19208 KB Output is correct
9 Correct 199 ms 19212 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 19224 KB Output is correct
2 Correct 99 ms 19236 KB Output is correct
3 Correct 97 ms 19332 KB Output is correct
4 Correct 98 ms 19368 KB Output is correct

Subtask #5
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 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -