Submission #456473

#	Time	Username	Problem	Language	Result	Execution time	Memory
456473		nafis_shifat	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1267 ms	86364 KiB

treearray

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define f first
#define s second
using namespace std;
const int mxn=2e5+5;
const int inf=1e9;
vector<int> adj[mxn];
int n,m,q;
int a[mxn];
int dp[20][mxn];
int level[mxn];
int T = 0;
int in[mxn];
int out[mxn];

int inv[mxn];
void dfs(int cur,int prev) {
    in[cur] = ++T;
    inv[T] = cur;
    dp[0][cur] = prev;
    level[cur] = level[prev] + 1;
    for(int i = 1; i < 20; i++) dp[i][cur] = dp[i - 1][dp[i - 1][cur]];
    for(int u : adj[cur]) {
        if(u != prev) dfs(u,cur);
    }
    out[cur] = T;
}



int getLCA(int u,int v) {
    if(level[u] < level[v]) swap(u,v);

    int dif = level[u] - level[v];
    for(int i = 0; i < 20; i++) if((dif >> i) & 1) u = dp[i][u];
    if(u == v) return v;
    for(int i = 19; i >= 0; i--) {
        if(dp[i][u] != dp[i][v]) {
            u = dp[i][u];
            v = dp[i][v];
        }
    }

    return dp[0][u];
}



set<int> pos1[mxn];
set<int> pos2[mxn];


int main() {

    cin >> n >> m >> q;

    for(int i = 1; i < n; i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i = 1; i <= m; i++) {
        scanf("%d",&a[i]);
        pos1[a[i]].insert(i);
    }

    
    
    

    dfs(1,0);

    for(int i = 1; i < m; i++) {
        pos2[getLCA(a[i],a[i + 1])].insert(i);
    }


  
    while(q--) {
        int tp;
        scanf("%d",&tp);

        if(tp == 1) {
            int p,v;
            scanf("%d%d",&p,&v);
            pos1[a[p]].erase(p);
            pos1[v].insert(p);

            if(p > 1) {
                int lca = getLCA(a[p - 1],a[p]);
                pos2[lca].erase(p - 1);
                pos2[getLCA(a[p - 1],v)].insert(p - 1);
            }

            if(p < m) {
                int lca = getLCA(a[p],a[p + 1]);
                pos2[lca].erase(p);
                pos2[getLCA(v,a[p + 1])].insert(p);
            }

            
            a[p] = v;


        }  else {
            int l,r,v;
            scanf("%d%d%d",&l,&r,&v);

            auto x = pos1[v].lower_bound(l);

            if(x != pos1[v].end() && *x <= r) {
                int k = *x;
                printf("%d %d\n",k,k);
                continue;
            }

            x = pos2[v].lower_bound(l);

            if(x != pos2[v].end() && *x < r) {
                int k = *x;
                printf("%d %d\n",k,k + 1);
            } else {
                printf("-1 -1\n");
            }
        }
    }










}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~
treearray.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
treearray.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%d",&tp);
      |         ~~~~~^~~~~~~~~~
treearray.cpp:90:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |             scanf("%d%d",&p,&v);
      |             ~~~~~^~~~~~~~~~~~~~
treearray.cpp:112:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |             scanf("%d%d%d",&l,&r,&v);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

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