oj.uz

Submission #103933

# Submission time Handle Problem Language Result Execution time Memory
103933 2019-04-03T10:05:34 Z MrTEK Min-max tree (BOI18_minmaxtree) C++14
22 / 100
 281 ms 20472 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 19740 KB Output is correct
2 Correct 262 ms 17144 KB Output is correct
3 Correct 258 ms 18724 KB Output is correct
4 Correct 250 ms 20472 KB Output is correct
5 Correct 257 ms 18168 KB Output is correct
6 Correct 281 ms 17672 KB Output is correct
7 Correct 213 ms 17224 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 131 ms 16208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4352 KB Output isn't correct
2 Halted 0 ms 0 KB -