Submission #1156878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156878		ivaziva	Birthday gift (IZhO18_treearray)	C++20	56 / 100	4091 ms	58520 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

#define MAXN 200001
#define MAXM 19

int n,m,q;
vector<int> adj[MAXN];
int a[MAXN],b[MAXN*2+5];
set<int> nodes[MAXN];
int dist[MAXN],parent[MAXM][MAXN];
queue<int> bfsq;

void bfs()
{
    for (int i=1;i<=n;i++) dist[i]=INT_MAX;
    dist[1]=0;bfsq.push(1);
    while (!bfsq.empty())
    {
        int node=bfsq.front();bfsq.pop();
        for (int sled:adj[node])
        {
            if (dist[sled]!=INT_MAX) continue;
            dist[sled]=dist[node]+1;parent[0][sled]=node;bfsq.push(sled);
        }
    }
}

int jump(int node,int k)
{
    for (int i=MAXM-1;i>=0;i--)
    {
        if (k<(1<<i)) continue;
        node=parent[i][node];k-=(1<<i);
    }
    return node;
}

int lca(int node1,int node2)
{
    if (dist[node1]<dist[node2]) swap(node1,node2);
    node1=jump(node1,dist[node1]-dist[node2]);
    if (node1==node2) return node1;
    for (int i=MAXM-1;i>=0;i--)
    {
        if (parent[i][node1]!=parent[i][node2]) {node1=parent[i][node1];node2=parent[i][node2];}
    }
    return parent[0][node1];
}

int main()
{
    ios_base::sync_with_stdio(false);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>q;
    for (int i=1;i<n;i++) {int x,y;cin>>x>>y;adj[x].push_back(y);adj[y].push_back(x);}
    for (int i=1;i<=m;i++) cin>>a[i];
    bfs();
    for (int j=1;j<MAXM;j++)
    {
        for (int i=1;i<=n;i++) parent[j][i]=parent[j-1][parent[j-1][i]];
    }
    for (int i=1;i<m;i++)
    {
        b[2*i-1]=a[i];nodes[b[2*i-1]].insert(2*i-1);
        b[2*i]=lca(a[i],a[i+1]);nodes[b[2*i]].insert(2*i);
    }
    b[2*m-1]=a[m];nodes[b[2*m-1]].insert(2*m-1);
    for (int i=1;i<=q;i++)
    {
        int type;cin>>type;
        if (type==1)
        {
            int pos,node;cin>>pos>>node;a[pos]=node;
            nodes[b[2*pos-1]].erase(2*pos-1);b[2*pos-1]=node;nodes[b[2*pos-1]].insert(2*pos-1);
            if (pos!=1) {nodes[b[2*pos-2]].erase(2*pos-2);b[2*pos-2]=lca(a[pos-1],a[pos]);nodes[b[2*pos-2]].insert(2*pos-2);}
            if (pos!=m) {nodes[b[2*pos]].erase(2*pos);b[2*pos]=lca(a[pos],a[pos+1]);nodes[b[2*pos]].insert(2*pos);}
        }
        else
        {
            int l,r,node;cin>>l>>r>>node;
            auto it=lower_bound(nodes[node].begin(),nodes[node].end(),2*l-1);
            if (it==nodes[node].end()) cout<<-1<<" "<<-1<<endl;
            else if ((*it)<=2*r-1)
            {
                if ((*it)%2==1) cout<<((*it)+1)/2<<" "<<((*it)+1)/2<<endl;
                else cout<<(*it)/2<<" "<<1+(*it)/2<<endl;
            }
            else cout<<-1<<" "<<-1<<endl;
        }
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 0 / 44