oj.uz

Submission #528162

# Submission time Handle Problem Language Result Execution time Memory
528162 2022-02-19T14:41:23 Z peuch Birthday gift (IZhO18_treearray) C++17
0 / 100
 12 ms 23780 KB 
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 10;
const int MAXL = 22;

int n, m, q;
int v[MAXN];
int prof[MAXN];
int dp[MAXN][MAXL];

vector<int> ar[MAXN];
set<int> loc[MAXN];
set<int> loc2[MAXN];

void preCalc(int cur);
int lca(int a, int b);

int main(){
  scanf("%d %d %d", &n, &m, &q);
  for(int i = 1; i < n; i++){
    int a, b;
    scanf("%d %d", &a, &b);
    ar[a].push_back(b);
    ar[b].push_back(a);
  }
  preCalc(1);
  for(int i = 1; i <= m; i++){
    scanf("%d", &v[i]);
    int anc = lca(v[i - 1], v[i]);
    loc[anc].insert(i - 1);
    loc2[v[i]].insert(i);
  }
  for(int i = 1; i <= q; i++){
    int t;
    scanf("%d", &t);
    if(t == 1){
      int a, b;
      scanf("%d %d", &a, &b);
      int anc;
      anc = lca(v[a], v[a + 1]);
      loc[anc].erase(a);
      anc = lca(v[a - 1], v[a]);
      loc[anc].erase(a - 1);
      loc2[v[a]].erase(a);
      v[a] = b;
      anc = lca(v[a], v[a + 1]);
      loc[anc].insert(a);
      anc = lca(v[a - 1], v[a]);
      loc[anc].insert(a - 1);
      loc2[v[a]].insert(a);
    }
    if(t == 2){
      int a, b, c;
      scanf("%d %d %d", &a, &b, &c);
      set<int> :: iterator it = loc[c].lower_bound(a);
      if(it == loc[c].end() || *it >= b){
        it = loc2[c].lower_bound(a);
        if(it == loc2[c].end() || *it >= b){
          printf("-1 -1\n");
          continue;
        }
        printf("%d %d\n", *it, *it);
        continue;
      }
      printf("%d %d\n", *it, *it + 1);
    }
  }
}

void preCalc(int cur){
  for(int k = 1; k < MAXL; k++)
    dp[cur][k] = dp[dp[cur][k - 1]][k - 1];
  for(int i = 0; i < ar[cur].size(); i++){
    int viz = ar[cur][i];
    if(viz == dp[cur][0]) continue;
    dp[viz][0] = cur;
    prof[viz] = prof[cur] + 1;
    preCalc(viz);
  }
}

int lca(int a, int b){
  if(prof[a] < prof[b]) swap(a, b);
  int d = prof[a] - prof[b];
  for(int k = 0; k < MAXL; k++)
    if((1 << k) & d) a = dp[a][k];
  if(a == b) return b;
  for(int k = MAXL - 1; k >= 0; k--)
    if(dp[a][k] != dp[b][k]) a = dp[a][k], b = dp[b][k];
  return dp[a][0];
}

Compilation message

treearray.cpp: In function 'void preCalc(int)':
treearray.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int i = 0; i < ar[cur].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~
treearray.cpp: In function 'int main()':
treearray.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%d %d %d", &n, &m, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%d %d", &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~
treearray.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d", &v[i]);
      |     ~~~~~^~~~~~~~~~~~~
treearray.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d", &t);
      |     ~~~~~^~~~~~~~~~
treearray.cpp:39:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |       scanf("%d %d", &a, &b);
      |       ~~~~~^~~~~~~~~~~~~~~~~
treearray.cpp:55:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |       scanf("%d %d %d", &a, &b, &c);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB n=5
2 Incorrect 12 ms 23780 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB n=5
2 Incorrect 12 ms 23780 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB n=5
2 Incorrect 12 ms 23780 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB n=5
2 Incorrect 12 ms 23780 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -