oj.uz

Submission #198852

# Submission time Handle Problem Language Result Execution time Memory
198852 2020-01-27T21:04:09 Z osaaateiasavtnl Synchronization (JOI13_synchronization) C++14
100 / 100
 375 ms 24440 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 2e5 + 7;
int n, m, q;
vector <int> g[N];
ii ed[N];
int tin[N], tout[N], ptr = 0, par[N], num[N];
void dfs(int u, int p) {
    par[u] = p;
    tin[u] = ++ptr;
    num[ptr] = u;
    for (int v : g[u]) 
        if (v != p)
            dfs(v, u);
    tout[u] = ptr;
}
int r[N << 2];
void upd(int v, int tl, int tr, int i, int x) {
    if (tl == tr) {
        r[v] = x;
        return;
    }
    int tm = (tl + tr) >> 1;
    if (i <= tm)
        upd(v * 2 + 1, tl, tm, i, x);
    else
        upd(v * 2 + 2, tm + 1, tr, i, x);
    r[v] = max(r[v * 2 + 1], r[v * 2 + 2]);
}   
int get(int v, int tl, int tr, int i) {
    if (i < tl || r[v] < i)
        return -1;
    if (tl == tr)
        return num[tl];
    int tm = (tl + tr) >> 1;
    int t = get(v * 2 + 2, tm + 1, tr, i);
    if (t != -1)
        return t;
    else
        return get(v * 2 + 1, tl, tm, i);
}   
int rep(int u) {
    return get(0, 1, n, tin[u]);        
}
int ans[N], last[N];
int get(int u) {
    return ans[rep(u)];
}   
bool cur[N];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> m >> q;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        ed[i] = mp(u, v);
        g[u].app(v); g[v].app(u);
    }   
    dfs(1, 1);
    for (int i = 0; i < n - 1; ++i) 
        if (par[ed[i].s] == ed[i].f)
            swap(ed[i].f, ed[i].s);
    for (int i = 1; i <= n; ++i)
        upd(0, 1, n, tin[i], tout[i]);
    for (int i = 1; i <= n; ++i)
        ans[i] = 1;
    while (m--) {
        int i;
        cin >> i;
        --i;
        #ifdef HOME
        cout << i + 1 << " : " << rep(ed[i].f) << ' ' << rep(ed[i].s) << '\n';
        #endif
        if (!cur[i]) {
            ans[rep(ed[i].s)] = ans[rep(ed[i].s)] + ans[rep(ed[i].f)] - last[i];
            upd(0, 1, n, tin[ed[i].f], -1);
        }
        else {
            last[i] = ans[ed[i].f] = get(ed[i].f);
            upd(0, 1, n, tin[ed[i].f], tout[ed[i].f]);
        }
        cur[i] ^= 1;
    }   
    while (q--) {
        int u; cin >> u;
        cout << get(u) << '\n';
    }    
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 8 ms 4984 KB Output is correct
5 Correct 9 ms 5112 KB Output is correct
6 Correct 10 ms 5240 KB Output is correct
7 Correct 23 ms 6392 KB Output is correct
8 Correct 24 ms 6520 KB Output is correct
9 Correct 23 ms 6392 KB Output is correct
10 Correct 306 ms 17248 KB Output is correct
11 Correct 276 ms 17412 KB Output is correct
12 Correct 253 ms 21368 KB Output is correct
13 Correct 235 ms 17388 KB Output is correct
14 Correct 197 ms 16632 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 18804 KB Output is correct
2 Correct 138 ms 18672 KB Output is correct
3 Correct 111 ms 20600 KB Output is correct
4 Correct 115 ms 20580 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct
3 Correct 9 ms 5112 KB Output is correct
4 Correct 8 ms 5116 KB Output is correct
5 Correct 9 ms 5112 KB Output is correct
6 Correct 10 ms 5240 KB Output is correct
7 Correct 25 ms 7032 KB Output is correct
8 Correct 267 ms 24400 KB Output is correct
9 Correct 276 ms 24440 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 21496 KB Output is correct
2 Correct 141 ms 23416 KB Output is correct
3 Correct 137 ms 23544 KB Output is correct
4 Correct 140 ms 23544 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 8 ms 5112 KB Output is correct
5 Correct 10 ms 5240 KB Output is correct
6 Correct 33 ms 6648 KB Output is correct
7 Correct 375 ms 20604 KB Output is correct
8 Correct 255 ms 24440 KB Output is correct
9 Correct 281 ms 20460 KB Output is correct
10 Correct 245 ms 19448 KB Output is correct
11 Correct 158 ms 21876 KB Output is correct
12 Correct 173 ms 22000 KB Output is correct
13 Correct 138 ms 23544 KB Output is correct