제출 #1157248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157248		ivaziva	Birthday gift (IZhO18_treearray)	C++20	56 / 100	4094 ms	67160 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];
set<int> nodes1[MAXN],nodes2[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)
{
    int stepen=0;
    while (k>0)
    {
        if (!(k&(1<<stepen))) {stepen++;continue;}
        node=parent[stepen][node];k-=(1<<stepen);stepen++;
    }
    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[i]=lca(a[i],a[i+1]);
    for (int i=1;i<=m;i++) nodes1[a[i]].insert(i);
    for (int i=1;i<m;i++) nodes2[b[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);a[pos]=node;nodes1[a[pos]].insert(pos);
            if (pos!=1) {nodes2[b[pos-1]].erase(pos-1);b[pos-1]=lca(a[pos-1],a[pos]);nodes2[b[pos-1]].insert(pos-1);}
            if (pos!=m) {nodes2[b[pos]].erase(pos);b[pos]=lca(a[pos],a[pos+1]);nodes2[b[pos]].insert(pos);}
        }
        else
        {
            int l,r,node;cin>>l>>r>>node;
            auto it1=lower_bound(nodes1[node].begin(),nodes1[node].end(),l);
            if (it1==nodes1[node].end())
            {
                auto it2=lower_bound(nodes2[node].begin(),nodes2[node].end(),l);
                if (it2==nodes2[node].end()) cout<<-1<<" "<<-1<<endl;
                else if ((*it2)<=r-1) cout<<(*it2)<<" "<<(*it2)+1<<endl;
                else cout<<-1<<" "<<-1<<endl;
            }
            else if ((*it1)<=r) cout<<(*it1)<<" "<<(*it1)<<endl;
            else
            {
                auto it2=lower_bound(nodes2[node].begin(),nodes2[node].end(),l);
                if (it2==nodes2[node].end()) cout<<-1<<" "<<-1<<endl;
                else if ((*it2)<=r-1) cout<<(*it2)<<" "<<(*it2)+1<<endl;
                else cout<<-1<<" "<<-1<<endl;
            }
        }
    }
}

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