제출 #443912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
443912		NintsiChkhaidze	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1929 ms	94640 KiB

treearray

#include <iostream>
#include <set>
#include <vector>
#define pb push_back
using namespace std;
const int N = 200005; 
int a[N],dp[N],d[20][N],n;
vector <int> v[N];
multiset <int> A[N],B[N];
void dfs(int x,int par){
    dp[x] = dp[par] + 1;
    d[0][x] = par;
    for (int i = 0; i < v[x].size(); i++)
      if (v[x][i] != par) dfs(v[x][i],x);
}
int lca(int x,int y){
    if (dp[x] > dp[y]) swap(x,y);
    for (int i = 18; i >= 0; i--)
        if (dp[d[i][y]] >= dp[x]) y = d[i][y];
  
    if (x == y) return x;
    for (int i = 18; i >= 0; i--)
        if (d[i][x] != d[i][y]) x = d[i][x],y = d[i][y];
  
    return d[0][x];
}
void upd(int ind,bool val){
    if (!ind) return;
    int y = lca(a[ind],a[ind + 1]),x = a[ind]; 
    
    if (!val){
        A[x].erase(A[x].find(ind));
        B[y].erase(B[y].find(ind));
    }
    else{
        A[x].insert(ind);
        B[y].insert(ind);
    }
}
int main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int m,q;
    cin>>n>>m>>q;
    
    for (int i = 1; i < n; i++){
        int a,b;
        cin>>a>>b;
        v[a].pb(b),v[b].pb(a);
    }
    for (int i = 1; i <= m; i++)
        cin>>a[i];
 
    dfs(1,1);
    for (int j = 1; j <= 18; j++)
        for (int i = 1; i <= n; i++)
            d[j][i] = d[j - 1][d[j - 1][i]];
 
    a[m + 1] = 1;
    for (int i = 1; i <= m; i++)
      upd(i,1);
    
    for (int i = 1; i <= n; i++)
        A[i].insert(N),B[i].insert(N);
   
    while(q--){
        int tp;
        cin>>tp;
        if (tp == 1){
            int pos,val;
            cin>>pos>>val;
            upd(pos - 1, 0); upd(pos, 0);
            a[pos] = val;
            upd(pos - 1, 1),upd(pos, 1);
        }
        else{
            int l,r,val;
            cin>>l>>r>>val;
            int x = *A[val].lower_bound(l);
            int y = *B[val].lower_bound(l);
            
            if (y >= l && y < r) cout<<y<<" "<<y + 1<<"\n";
            else if (x >= l && x <= r) cout<<x<<" "<<x<<"\n";
            else cout<<-1<<" "<<-1<<"\n";
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:13:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i = 0; i < v[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~

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