Submission #202653

#	Time	Username	Problem	Language	Result	Execution time	Memory
202653		quocnguyen1012	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1625 ms	74940 KiB

treearray

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 5;

vector<int> adj[maxn];
int N, M, Q;
int a[maxn], depth[maxn], par[maxn][20];
set<pair<int, int>> can[maxn];

void prepare(int u, int p = -1)
{
  for (int i = 1; (1 << i) <= N; ++i)
    par[u][i] = par[par[u][i - 1]][i - 1];
  for (int v : adj[u]) if (v != p){
    depth[v] = depth[u] + 1;
    par[v][0] = u;
    prepare(v, u);
  }
}

int LCA(int x, int y)
{
  if (depth[x] < depth[y]) swap(x, y);
  for (int k = 19; k >= 0; --k){
    if (depth[par[x][k]] >= depth[y]){
      x = par[x][k];
    }
  }
  if (x == y) return x;
  for (int k = 19; k >= 0; --k){
    if (par[x][k] != par[y][k]){
      x = par[x][k];
      y = par[y][k];
    }
  }
  return par[x][0];
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> M >> Q;
  for (int i = 1; i < N; ++i){
    int u, v; cin >> u >> v;
    adj[u].pb(v); adj[v].pb(u);
  }
  depth[1] = 1;
  prepare(1);
  for (int i = 1; i <= M; ++i){
    cin >> a[i];
    can[a[i]].insert(mp(i, i));
    if (i > 1){
      can[LCA(a[i], a[i - 1])].insert(mp(i - 1, i));
    }
  }
  while (Q--){
    int type; cin >> type;
    if (type == 1){
      int i, v; cin >> i >> v;
      can[a[i]].erase(mp(i, i));
      if (i > 1) can[LCA(a[i], a[i - 1])].erase(mp(i - 1, i));
      if (i < M) can[LCA(a[i], a[i + 1])].erase(mp(i, i + 1));
      a[i] = v;
      can[a[i]].insert(mp(i, i));
      if (i > 1) can[LCA(a[i], a[i - 1])].insert(mp(i - 1, i));
      if (i < M) can[LCA(a[i], a[i + 1])].insert(mp(i, i + 1));
    }
    else{
      int L, R, v; cin >> L >> R >> v;
      auto it = can[v].lower_bound(mp(L, 0));
      int l = -1, r = -1;
      if (it != can[v].end() && it -> se <= R){
        l = it -> fi;
        r = it -> se;
      }
      cout << l << ' ' << r << '\n';
    }
  }
}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:51:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
treearray.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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