제출 #97534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97534		Alexa2001	동기화 (JOI13_synchronization)	C++17	100 / 100	783 ms	24440 KiB

synchronization

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40