Submission #86935

#	Time	Username	Problem	Language	Result	Execution time	Memory
86935		long10024070	Synchronization (JOI13_synchronization)	C++11	100 / 100	355 ms	19328 KiB

synchronization

#define Link "https://oj.uz/problem/view/JOI13_synchronization?fbclid=IwAR13-gsTQ4n3SSIS6NzUA_X7iaFxN_3aJYCyIeVRZb88iIzHhvMV6K31H-M"

#include <iostream>
#include <cstdio>
#include <vector>

#define TASK "Synchronization"

using namespace std;

const int maxn = 1e5 + 1;
int n,m,q,_u[maxn],_v[maxn],h[maxn],st[maxn],en[maxn],cnt,True[maxn],f[maxn],mem[maxn];
vector <int> e[maxn];
struct T_node
{
    int l,r,mx;
} node[maxn*6];
bool b[maxn];

void Enter()
{
    cin >> n >> m >> q;
    for (int i=1;i<n;++i) {
        cin >> _u[i] >> _v[i];
        e[_u[i]].push_back(_v[i]);
        e[_v[i]].push_back(_u[i]);
    }
}

void DFS(int u, int p)
{
    h[u] = h[p] + 1;
    st[u] = en[u] = ++cnt;
    True[st[u]] = u;
    for (int v : e[u])
        if (v != p) {
            DFS(v,u);
            en[u] = en[v];
        }
}

void Init()
{
    DFS(1,0);
    for (int i=1;i<=n;++i)
        if (h[_u[i]] > h[_v[i]])
            swap(_u[i],_v[i]);
}

void Build_tree(int i, int l, int r)
{
    node[i].l = l;
    node[i].r = r;
    if (l != r) {
        Build_tree(i*2,l,(l+r)/2);
        Build_tree(i*2+1,(l+r)/2+1,r);
        node[i].mx = max(node[i*2].mx,node[i*2+1].mx);
    }
    else
        node[i].mx = en[True[l]];
}

int Query(int i, int id)
{
    if (st[id] < node[i].l || node[i].mx < en[id])
        return 0;
    if (node[i].l == node[i].r)
        return node[i].l;
    else {
        int x = Query(i*2+1,id);
        if (x != 0)
            return x;
        return Query(i*2,id);
    }
}

void Update(int i, int id, int val)
{
    if (node[i].r < id || id < node[i].l)
        return;
    if (node[i].l == node[i].r)
        node[i].mx = val;
    else {
        Update(i*2,id,val);
        Update(i*2+1,id,val);
        node[i].mx = max(node[i*2].mx,node[i*2+1].mx);
    }
}

void Solve()
{
    fill(f,f+n+1,1);
    Build_tree(1,1,n);
    for (;m>0;--m) {
        int i;
        cin >> i;
        int cp = True[Query(1,_u[i])];
        if (b[i]) {
            f[_v[i]] = mem[_v[i]] = f[cp];
            Update(1,st[_v[i]],en[_v[i]]);
        }
        else {
            f[cp] += f[_v[i]] - mem[_v[i]];
            Update(1,st[_v[i]],0);
        }
        b[i] ^= 1;
    }
    for (int i=1;i<=n;++i)
        if (b[i]) {
            int cp = True[Query(1,_u[i])];
            Update(1,st[_v[i]],en[_v[i]]);
            f[_v[i]] = mem[_v[i]] = f[cp];
            b[i] = 0;
        }
    for (;q>0;--q) {
        int u;
        cin >> u;
        cout << f[u] << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

#ifdef LHL
    freopen(".INP","r",stdin);
    freopen(".OUT","w",stdout);
#else
//    freopen(TASK".INP","r",stdin);
//    freopen(TASK".OUT","w",stdout);
#endif // LHL

    Enter();
    Init();
    Solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40