Submission #1156869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156869		ivaziva	Birthday gift (IZhO18_treearray)	C++20	0 / 100	11 ms	23876 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],lca[MAXN];
set<int> nodes[MAXN],nodes1[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 nodelca(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()
{
    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];nodes1[a[i]].insert(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++) {lca[i]=nodelca(a[i],a[i+1]);nodes[lca[i]].insert(i);}
    for (int i=1;i<=q;i++)
    {
        int type;cin>>type;
        if (type==1)
        {
            int pos,node;cin>>pos>>node;
            nodes1[a[pos]].erase(pos);nodes1[node].insert(pos);a[pos]=node;
            if (pos==1) {nodes[lca[1]].erase(1);lca[1]=nodelca(a[1],a[2]);nodes[lca[1]].insert(1);}
            else if (pos==m) {nodes[lca[m-1]].erase(m-1);lca[m-1]=nodelca(a[m-1],a[m]);nodes[lca[m-1]].insert(m-1);}
            else
            {
                nodes[lca[i-1]].erase(i-1);lca[i-1]=nodelca(a[i-1],a[i]);nodes[lca[i-1]].insert(i-1);
                nodes[lca[i]].erase(i);lca[i]=nodelca(a[i],a[i+1]);nodes[lca[i]].insert(i);
            }
        }
        else
        {
            int l,r,node;cin>>l>>r>>node;
            auto it=lower_bound(nodes[node].begin(),nodes[node].end(),l);
            if (it==nodes[node].end())
            {
                auto it1=lower_bound(nodes1[node].begin(),nodes1[node].end(),l);
                if (it1==nodes1[node].end()) cout<<-1<<" "<<-1<<endl;
                else if ((*it1)<=r) cout<<(*it1)<<" "<<(*it1)<<endl;
                else cout<<-1<<" "<<-1<<endl;
            }
            else if ((*it)<=r-1) cout<<(*it)<<" "<<(*it)+1<<endl;
            else
            {
                auto it1=lower_bound(nodes1[node].begin(),nodes1[node].end(),l);
                if (it1==nodes1[node].end()) cout<<-1<<" "<<-1<<endl;
                else if ((*it1)<=r) cout<<(*it1)<<" "<<(*it1)<<endl;
                else cout<<-1<<" "<<-1<<endl;
            }
        }
    }
}

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