Submission #1201734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201734		ElayV13	Birthday gift (IZhO18_treearray)	C++20	0 / 100	3 ms	5188 KiB

treearray

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e18;
const int M = 2e5 + 1;
const int LOG = 20;

int n , m , q , a[M] , up[LOG][M] , dep[M];
vector < int > adj[M];

void dfs(int v , int p)
{
        up[0][v] = p;
        for(int i = 1;i < LOG;i++) up[i][v] = up[i - 1][up[i - 1][v]];
        for(int u : adj[v]){
                if(u == p) continue;
                dep[u] = dep[v] + 1;
                dfs(u , v);
        }
}

int LCA(int a , int b)
{
        if(dep[a] < dep[b]) swap(a , b);
        int dif = dep[a] - dep[b];
        for(int i = 0;i < LOG;i++)
        {
                if((1 << i) & dif)
                {
                        a = up[i][a];
                }
        }
        if(a == b) return a;
        for(int i = LOG - 1;i >= 0;i--)
        {
                if(up[i][a] != up[i][b])
                {
                        a = up[i][a];
                        b = up[i][b];
                }
        }
        return up[0][a];
}

signed main()
{
      ios_base::sync_with_stdio(0);cin.tie(0);
      cin >> n >> m >> q;
      for(int i = 2;i <= n;i++)
      {
              int u , v;
              cin >> u >> v;
              adj[u].push_back(v);
              adj[v].push_back(u);
      }
      for(int i = 1;i <= m;i++) cin >> a[i];
      dfs(1 , -1);
      while(q--)
      {
              int t;
              cin >> t;
              if(t == 1)
              {
                      int pos , v;
                      cin >> pos >> v;
                      a[pos] = v;
              }
              else
              {
                      int l , r , v;
                      cin >> l >> r >> v;
                      bool ok = 0;
                      for(int i = l;i <= r;i++)
                      {
                              if(a[i] == v)
                              {
                                      cout << i << ' ' << i << endl;
                                      ok = 1;
                                      break;
                              }
                      }
                      if(ok) continue;
                      vector < int > p(m + 1 , 0);
                      for(int i = l;i <= r;i++) p[i] = (LCA(v , a[i]) == v);
                      for(int i = 2;i <= m;i++) p[i] += p[i - 1];
                      vector < int > anc(m + 1 , -1);
                      for(int i = l;i <= r;i++)
                      {
                              if(LCA(v , a[i]) == v)
                              {
                                      for(int u : adj[v])
                                      {
                                              if(LCA(u , a[i]) == u) anc[i] = u;
                                      }
                              }
                      }
                      bool can = 0;
                      for(int i = l;i <= r;i++)
                      {
                              int lo = i , hi = r , mx = -INF;
                              while(lo <= hi){
                                        int mi = (lo + hi) >> 1;
                                        if(p[mi] - p[i - 1] == mi - i + 1)
                                        {
                                                mx = max(mx , mi);
                                                lo = mi + 1;
                                        }
                                        else hi = mi - 1;
                              }
                              if(mx == -INF) continue;
                              for(int j = i;j <= mx;j++)
                              {
                                      if(anc[i] != anc[j] && anc[j] != -1 && anc[i] != -1)
                                      {
                                              cout << i << ' ' << j << endl;
                                              can = 1;
                                              break;
                                      }
                              }
                              if(can) break;
                      }
                      if(!can)
                      {
                              cout << -1 << ' ' << -1 << endl;
                      }
              }
      }
}

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