oj.uz

Submission #659833

# Submission time Handle Problem Language Result Execution time Memory
659833 2022-11-19T11:45:05 Z Ronin13 Synchronization (JOI13_synchronization) C++14
100 / 100
 423 ms 21364 KB 
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;

const int nmax = 2e5 + 1;

int a[nmax], b[nmax];
int in[nmax];
int out[nmax];
vector <int> t(4 * nmax);

void update(int v, int l, int r, int pos, int val){
    if(l > pos || r < pos) return;
    if(l == r){
        t[v] = val;
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, val);
    update(2 * v + 1, m+ 1, r, pos, val);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}

int getlast(int v, int l, int r, int st, int fin, int val){
    if(l > fin || r < st) return -1;
    if(l >= st && r <= fin){
        if(t[v] < val) return -1;
        while(l != r){
            int m = (l + r) / 2;
            if(t[2 * v + 1] >= val) v = v * 2 + 1, l = m + 1;
            else v = v * 2, r = m;
        }
        return l;
    }
    int m = (l + r) / 2;
    int u = getlast(2 * v + 1, m + 1, r, st, fin, val);
    if(u != -1) return u;
    return getlast(2 * v, l, m, st, fin, val);
}

int timer = 1;
int timer1 = 1;
vector <vector <int> > g(nmax);
void dfs(int v, int e = -1){
    in[v] = timer++;
    for(int to : g[v]){
        if(to == e) continue;
        dfs(to, v);
    }
    out[v] = timer1++;
}

int n;

void add(int v, int o){
    int u = getlast(1, 1, n, 1, v - 1, o);
    a[u] = a[v] + a[u] - b[v];
    update(1, 1, n, v, 0);
}

void rem(int v, int o){
    int u = getlast(1, 1, n, 1, v, o);
    b[v] = a[u];
    a[v] = a[u];
    update(1, 1, n, v, o);
}

int main(){
    #ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    #endif // ONLINE_JUDGE
    cin >> n;
    int m; cin >> m;
    int q; cin >> q;
    pii ed[n];
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
        ed[i] = {u, v};
    }
    dfs(1);
    for(int i= 1; i <= n; i++){
        update(1, 1, n, in[i], out[i]);
        a[i] = 1;
    }
    for(int i = 1; i < n; i++){
        int &u = ed[i].f, &v = ed[i].s;
        if(in[u] < in[v]) swap(ed[i].f, ed[i].s);
    }

    bool cond[n];
    fill(cond, cond + n, false);
    while(m--){
        int x; cin >> x;
        int u = ed[x].f;
        int v = ed[x].s;
        cond[x] ^= 1;
        if(cond[x]) add(in[u], out[u]);
        else rem(in[u], out[u]);
       /* for(int i = 1; i <= n; i++)
            cout << a[i] << ' ';
        cout << "\n";*/
    }
    for(int i = 1; i <= q; i++){
        int v; cin >> v;
        int o = getlast(1, 1, n, 1, in[v], out[v]);
        cout << a[o] << "\n";
    }
    return 0;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:105:13: warning: unused variable 'v' [-Wunused-variable]
  105 |         int v = ed[x].s;
      |             ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 6 ms 8036 KB Output is correct
3 Correct 5 ms 8152 KB Output is correct
4 Correct 6 ms 8148 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct
6 Correct 7 ms 8160 KB Output is correct
7 Correct 24 ms 8848 KB Output is correct
8 Correct 24 ms 8860 KB Output is correct
9 Correct 26 ms 8816 KB Output is correct
10 Correct 245 ms 16132 KB Output is correct
11 Correct 274 ms 16060 KB Output is correct
12 Correct 233 ms 20620 KB Output is correct
13 Correct 208 ms 16076 KB Output is correct
14 Correct 189 ms 15116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 16612 KB Output is correct
2 Correct 169 ms 17748 KB Output is correct
3 Correct 139 ms 19652 KB Output is correct
4 Correct 142 ms 19684 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8152 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 5 ms 8148 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct
6 Correct 7 ms 8292 KB Output is correct
7 Correct 38 ms 9524 KB Output is correct
8 Correct 388 ms 21364 KB Output is correct
9 Correct 380 ms 21356 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 20116 KB Output is correct
2 Correct 338 ms 20788 KB Output is correct
3 Correct 294 ms 20840 KB Output is correct
4 Correct 301 ms 20916 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 5 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 8 ms 8164 KB Output is correct
6 Correct 40 ms 8932 KB Output is correct
7 Correct 423 ms 16948 KB Output is correct
8 Correct 384 ms 21328 KB Output is correct
9 Correct 368 ms 17152 KB Output is correct
10 Correct 339 ms 16344 KB Output is correct
11 Correct 332 ms 19096 KB Output is correct
12 Correct 355 ms 19024 KB Output is correct
13 Correct 289 ms 20856 KB Output is correct