Submission #103933

#	Time	Username	Problem	Language	Result	Execution time	Memory
103933		MrTEK	Min-max tree (BOI18_minmaxtree)	C++14	22 / 100	281 ms	20472 KiB

minmaxtree

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 1e5 + 5;
const int LOG = 18;
const int inf = 1e9;

vector <int> ed[N];
int q,x[N],y[N],n,dep[N],dad[N][LOG + 1],st[N],tree[N << 2],sub[N],head[N],tim;

int calc(int cur = 1,int back = 0) {
  dep[cur] = dep[back] + 1;
  dad[cur][0] = back;
  for (int i = 1 ; i <= LOG ; i++)
    dad[cur][i] = dad[dad[cur][i - 1]][i - 1];
  for (auto i : ed[cur])
    if (i != back)
      sub[cur] += calc(i,cur);
  return ++sub[cur];
}

void dfs(int cur = 1,int back = 0,int curhead = 1) {
  head[cur] = curhead;
  st[cur] = ++tim;
  int go = 0;
  for (auto i : ed[cur])
    if (i != back && sub[i] >= sub[go])
      go = i;
  if (go)
    dfs(go,cur,curhead);
  for (auto i : ed[cur])
    if (i != back && i != go)
      dfs(i,cur,i);
}

int get_lca(int x,int y) {
  if (dep[x] < dep[y])
    swap(x,y);
  for (int i = LOG - 1 ; i >= 0 ; i--)
    if (dep[dad[x][i]] >= dep[y])
      x = dad[x][i];
  if (x == y)
    return x;
  for (int i = LOG - 1 ; i >= 0 ; i--)
    if (dad[x][i] != dad[y][i])
      x = dad[x][i],
      y = dad[y][i];
  return dad[x][0];
}

void update(int ind,int l,int r,int lw,int rw,int val) {
  if (l > rw || r < lw)
    return;
  if (l >= lw && r <= rw) {
    tree[ind] = min(tree[ind],val);
    return;
  }
  int mid = (l + r) / 2;
  update(ind + ind,l,mid,lw,rw,val);
  update(ind + ind + 1,mid + 1,r,lw,rw,val);
}

int query(int ind,int l,int r,int w) {
  if (l > w || r < w)
    return inf;
  if (l == w && r == w)
    return tree[ind];
  int mid = (l + r) / 2;
  return min(tree[ind],min(query(ind + ind,l,mid,w),query(ind + ind + 1,mid + 1,r,w)));
}

void update(int u,int v,int val) {
  int lca = get_lca(u,v);
  while(u != lca) {
    if (dep[head[u]] <= dep[lca]) {
      update(1,1,n,st[lca] + 1,st[u],val);
      break;
    }
    update(1,1,n,st[head[u]],st[u],val);
    u = dad[head[u]][0];
  }
  while(v != lca) {
    if (dep[head[v]] <= dep[lca]) {
      update(1,1,n,st[lca] + 1,st[v],val);
      break;
    }
    update(1,1,n,st[head[v]],st[v],val);
    v = dad[head[v]][0];
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n;
  for (int i = 1 ; i < n ; i++) {
    cin >> x[i] >> y[i];
    ed[x[i]].push_back(y[i]);
    ed[y[i]].push_back(x[i]);
  }
  calc();
  dfs();
  for (int i = 0 ; i < (N << 2) ; i++)
    tree[i] = inf;
  cin >> q;
  while(q--) {
    char ch;
    int u,v,val;
    cin >> ch >> u >> v >> val;
    update(u,v,val);
  }
  for (int i = 1 ; i < n ; i++) {
    if (dep[x[i]] < dep[y[i]])
      swap(x[i],y[i]);
    cout << x[i] << " " << y[i] << " " << query(1,1,n,st[x[i]]) << "\n";
  }
}

• Subtask 1: 0 / 7
• Subtask 2: 22 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42