Submission #44005

#	Time	Username	Problem	Language	Result	Execution time	Memory
44005		Nordway	Birthday gift (IZhO18_treearray)	C++14	30 / 100	4041 ms	26852 KiB

treearray

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string.h>
#include <stdio.h>
#include <assert.h>

using namespace std;

typedef long long LL;
typedef map<string , int> MSI;
typedef vector<int> VI;
typedef pair<int, int> PII;

#define endl '\n'
#define pb(x) push_back(x)
#define sqr(x) ((x) * (x))
#define F first
#define S second
#define SZ(t) ((int) t.size())
#define len(t) ((int) t.length())
#define base LL(1e9 + 7)
#define fname ""
#define sz 1000 * 1000
#define EPS (1e-8)
#define INF ((int)1e9 + 9)
#define mp make_pair

int tin[sz], T, tout[sz], n, k, q, b[sz], p[sz];
VI a[sz];

bool upper(int v, int u) {
  return tin[v] <= tin[u] && tout[u] <= tout[v];
}

void dfs(int v, int pr = 0) {
  tin[v] = ++T;
  p[v] = pr;
  for (int i = 0; i < a[v].size(); i++) {
    int to = a[v][i];
    if (to == pr) continue;
    dfs(to, v);
  }
  tout[v] = ++T;
}

int main()
{
//    freopen(fname"in", "r", stdin);
//    freopen(fname"out", "w", stdout);

  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cin >> n >> k >> q;
  for (int i = 2; i <= n; i++) {
    int v, u;
    cin >> v >> u;
    a[v].pb(u);
    a[u].pb(v);
  }

  for (int i = 1; i <= k; i++) {
    cin >> b[i];
  }
  dfs(1);
  tout[0] = 1e9;

  int l, r, x, ty;
  for (int i = 1; i <= q; i++) {
    cin >> ty;
    if (ty == 1) {
      cin >> l >> x;
      b[l] = x;
    } else {
      cin >> l >> r >> x;
      int f = 0;
      for (int L = l; !f && L <= r; L++) {
        int cur = b[L];
        for (int R = L; !f && R <= r; R++) {
          while (!upper(cur, b[R])) cur = p[cur];
          if (!upper(x, cur)) break;
          if (cur == x) {
            f = 1;
            cout << L << " " << R << "\n";
          }
        }
      }
      if (!f)
        cout << -1 << " " << -1 << "\n";
    }
  }

}

Compilation message (stderr)

treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:56:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a[v].size(); i++) {
                   ~~^~~~~~~~~~~~~

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