oj.uz

Submission #597525

# Submission time Handle Problem Language Result Execution time Memory
597525 2022-07-16T08:41:52 Z AA_Surely Synchronization (JOI13_synchronization) C++17
50 / 100
 8000 ms 19480 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
#define endl '\n'

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

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) {
        //cout << "now on : " << ls << ' ' << rs << endl;
        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) {
    t[now] = cnt++;
    order.pb(now);
    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, -1);
    F0R(i, n) sort(ALL(adj[i]), [](const PII &a, const PII &b){return sz[a.S] > sz[b.S];});
    iota(head, head + n, 0);

    dfs(0);

    fill(ans, ans + n, 1);

    return;
}

int grand(int v) {
    //cout << "now on : " << v + 1 << " with head " << head[v] << endl;
    int pl = tree.rightest(t[v]);
    //cout << "rightest is " << pl + 1 << endl;
    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];
    //cout << "ans[" << p + 1 << "] = " << ans[p] << endl;
    tree.change(t[ eset[x].S ], 1);
    //cout << "changing t[" << eset[x].S + 1 << "] to 1" << endl;

    exist[x] = 1;
    return;
}

int main() {
    IOS;

    init();
    rebuild();
    
    //F0R(i, n) cout << head[i] << ' '; cout << endl;

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

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 8041 ms 4948 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 16104 KB Output is correct
2 Correct 83 ms 16104 KB Output is correct
3 Correct 68 ms 18868 KB Output is correct
4 Correct 61 ms 18756 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 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 14 ms 6484 KB Output is correct
8 Correct 148 ms 19332 KB Output is correct
9 Correct 141 ms 19352 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 19328 KB Output is correct
2 Correct 84 ms 19292 KB Output is correct
3 Correct 84 ms 19412 KB Output is correct
4 Correct 83 ms 19480 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 8067 ms 4980 KB Time limit exceeded
3 Halted 0 ms 0 KB -