oj.uz

Submission #97534

# Submission time Handle Problem Language Result Execution time Memory
97534 2019-02-16T20:31:17 Z Alexa2001 Synchronization (JOI13_synchronization) C++17
100 / 100
 783 ms 24440 KB 
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e5 + 5, lg = 18;

vector<int> v[Nmax];
pair<int,int> E[Nmax];

bool active[Nmax];
int t[lg+2][Nmax], In[Nmax], Out[Nmax], level[Nmax];
int tmp, n;
int cnt[Nmax], cnt2[Nmax];


class AIB
{
    int a[Nmax];
    int ub(int x) { return (x&(-x)); }
public:
    void upd(int x, int add)
    {
        for(; x<=n; x+=ub(x)) a[x] += add;
    }

    int query(int x)
    {
        int ans = 0;
        for(; x; x-=ub(x)) ans += a[x];
        return ans;
    }

    int query(int x, int y)
    {
        return query(y) - query(x-1);
    }
} aib;

void dfs(int node, int dad = 0)
{
    int i;
    t[0][node] = dad;
    for(i=1; i<=lg; ++i) t[i][node] = t[i-1][t[i-1][node]];

    level[node] = level[dad] + 1;
    In[node] = ++tmp;
    for(auto it : v[node])
        if(it != dad)
        {
            dfs(it, node);

        }
    Out[node] = tmp;
}

void go_up(int &node)
{
    int i;
    for(i=lg; i>=0; --i)
    {
        int x = t[i][node];
        if(aib.query(In[x] + 1, In[node]) == level[node] - level[x])
            node = t[i][node];
    }
}

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    int i, m, q, id, x, y;

    cin >> n >> m >> q;
    for(i=1; i<n; ++i)
    {
        cin >> x >> y;
        E[i] = {x, y};
        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(1);

    for(i=1; i<=n; ++i) cnt[i] = 1, cnt2[i] = 0;

    while(m--)
    {
        cin >> id;
        tie(x, y) = E[id];
        if(level[x] > level[y]) swap(x, y);

        go_up(x);

        if(!active[id])
        {
            cnt[x] += (cnt[y] - cnt2[y]);
            aib.upd(In[y], +1);
            aib.upd(Out[y] + 1, -1);
        }
        else
        {
            aib.upd(In[y], -1);
            aib.upd(Out[y] + 1, +1);
            cnt[y] = cnt2[y] = cnt[x];
        }
        active[id] ^= 1;
    }

    while(q--)
    {
        cin >> x; go_up(x);
        cout << cnt[x] << '\n';
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 6 ms 2816 KB Output is correct
5 Correct 5 ms 2816 KB Output is correct
6 Correct 7 ms 2944 KB Output is correct
7 Correct 22 ms 4352 KB Output is correct
8 Correct 27 ms 4436 KB Output is correct
9 Correct 23 ms 4352 KB Output is correct
10 Correct 704 ms 19208 KB Output is correct
11 Correct 553 ms 19064 KB Output is correct
12 Correct 683 ms 23560 KB Output is correct
13 Correct 139 ms 18800 KB Output is correct
14 Correct 346 ms 18424 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 21252 KB Output is correct
2 Correct 93 ms 20984 KB Output is correct
3 Correct 111 ms 22904 KB Output is correct
4 Correct 118 ms 22904 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct
3 Correct 5 ms 2816 KB Output is correct
4 Correct 5 ms 2816 KB Output is correct
5 Correct 5 ms 2816 KB Output is correct
6 Correct 8 ms 3072 KB Output is correct
7 Correct 45 ms 4984 KB Output is correct
8 Correct 783 ms 24360 KB Output is correct
9 Correct 682 ms 24336 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 24336 KB Output is correct
2 Correct 346 ms 24088 KB Output is correct
3 Correct 305 ms 24116 KB Output is correct
4 Correct 351 ms 24076 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct
3 Correct 5 ms 2816 KB Output is correct
4 Correct 5 ms 2816 KB Output is correct
5 Correct 8 ms 2944 KB Output is correct
6 Correct 42 ms 4480 KB Output is correct
7 Correct 773 ms 19864 KB Output is correct
8 Correct 751 ms 24440 KB Output is correct
9 Correct 320 ms 19980 KB Output is correct
10 Correct 562 ms 19832 KB Output is correct
11 Correct 276 ms 22448 KB Output is correct
12 Correct 296 ms 22364 KB Output is correct
13 Correct 341 ms 24344 KB Output is correct