oj.uz

Submission #63618

# Submission time Handle Problem Language Result Execution time Memory
63618 2018-08-02T09:15:21 Z Just_Solve_The_Problem Min-max tree (BOI18_minmaxtree) C++11
100 / 100
 707 ms 60948 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ok puts("ok");
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair

const int N = (int)2e5 + 7;
const int inf = (int)1e9 + 7;

struct T {
  pii mn, mx;
  pii addmx, addmn;
  T() {
    mn = mk(-1, 0);
    mx = mk(inf, 0);
    addmn = mk(-1, 0);
    addmx = mk(inf, 0);
  }
};
T tree[N * 4];

struct query {
  int tp, a, b, val;
  query() {}
  query(int _tp, int _a, int _b, int _val) {
    tp = _tp;
    a = _a;
    b = _b;
    val = _val;
  }
};
query asq[N];

void push(int v, int l, int r) {
  if (tree[v].addmn.fr != -1) {
    if (l != r) {
      tree[v + v].addmn = max(tree[v + v].addmn, tree[v].addmn);
      tree[v + v + 1].addmn = max(tree[v + v + 1].addmn, tree[v].addmn);
    }
    tree[v].mn = max(tree[v].mn, tree[v].addmn);
    tree[v].addmn.fr = -1;
  }
  if (tree[v].addmx.fr != inf) {
    if (l != r) {
      tree[v + v].addmx = min(tree[v + v].addmx, tree[v].addmx);
      tree[v + v + 1].addmx = min(tree[v + v + 1].addmx, tree[v].addmx);
    }
    tree[v].mx = min(tree[v].mx, tree[v].addmx);
    tree[v].addmx.fr = inf;
  }
}

int n;
int asd;

// tp = 1, min
// tp = 2, MAX

void upd(int tp, int l, int r, int val, int v = 1, int tl = 1, int tr = n) {
  push(v, tl, tr);
  if (tl > r || tr < l) return ;
  if (l <= tl && tr <= r) {
    if (tp == 1) {
      tree[v].addmn = max(tree[v].addmn, mk(val, asd));
    } else if (tp == 2) {
      tree[v].addmx = min(tree[v].addmx, mk(val, asd));
    }
    push(v, tl, tr);
    return ;
  }
  int mid = (tl + tr) >> 1;
  upd(tp, l, r, val, v + v, tl, mid);
  upd(tp, l, r, val, v + v + 1, mid + 1, tr);
}

pii ar1[N], ar2[N];
int poss[N];

void buildget(int v = 1, int l = 1, int r = n) {
  push(v, l, r);
  if (l == r) {
    ar1[poss[l]] = tree[v].mx;
    ar2[poss[l]] = tree[v].mn;
    return ;
  }
  int mid = (l + r) >> 1;
  buildget(v + v, l, mid);
  buildget(v + v + 1, mid + 1, r);
}

vector < int > gr[N], gr1[N + N];
int pr[N];
int sz[N];
int chainpos[N], chain[N], chainsz[N], head[N];
int chsz = 1;
int lca[18][N];
int tin[N], tout[N];
int tiktak = 0, cur = 1;
int mt[N];
int used[N];
int prr[N + N];

void getsz(int v) {
  sz[v] = 1;
  tin[v] = ++tiktak;
  lca[0][v] = pr[v];
  for (int i = 1; i <= 17; i++) {
    lca[i][v] = lca[i - 1][lca[i - 1][v]];
  }
  for (int to : gr[v]) {
    if (to == pr[v]) continue;
    pr[to] = v;
    getsz(to);
    sz[v] += sz[to];
  }
  tout[v] = tiktak;
}

void build(int v, int ch) {
  poss[cur] = v;
  chainpos[v] = cur++;
  chainsz[ch]++;
  chain[v] = ch;
  if (chainsz[ch] == 1) {
    head[ch] = v;
  }
  int big = 0;
  for (int to : gr[v]) {
    if (to == pr[v]) continue;
    if (sz[to] > sz[big]) {
      big = to;
    }
  }
  if (big)
    build(big, ch);
  for (int to : gr[v]) {
    if (to == pr[v] || to == big) continue;
    build(to, ++chsz);
  }
}

bool upper(int a, int b) {
  return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int getlca(int a, int b) {
  if (upper(a, b)) return a;
  if (upper(b, a)) return b;
  for (int i = 17; i >= 0; i--) {
    if (!upper(lca[i][a], b)) a = lca[i][a];
  }
  return lca[0][a];
}

void updm(int tp, int a, int b, int val) {
  int lc = getlca(a, b);
  while (chain[a] != chain[lc]) {
    upd(tp, chainpos[head[chain[a]]], chainpos[a], val);
    a = pr[head[chain[a]]];
  }
  while (chain[b] != chain[lc]) {
    upd(tp, chainpos[head[chain[b]]], chainpos[b], val);
    b = pr[head[chain[b]]];
  }
  if (chainpos[lc] + 1 <= max(chainpos[b], chainpos[a])) {
    upd(tp, chainpos[lc] + 1, max(chainpos[a], chainpos[b]), val);
  }
}

bool kuhn(int v) {
  if (used[v]) return 0;
  used[v] = 1;
  for (int to : gr1[v]) {
    if (mt[to] == -1 || kuhn(mt[to])) {
      mt[to] = v;
      prr[v] = to;
      return 1;
    }
  }
  return 0;
}

main() {
  memset(mt, -1, sizeof mt);
  memset(prr, -1, sizeof prr);
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int v, u;
    scanf("%d %d", &v, &u);
    gr[v].pb(u);
    gr[u].pb(v);
  }
  pr[1] = 1;
  getsz(1);
  build(1, 1);
  int q;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    asd = i;
    char c;
    scanf("\n");
    int a, b, x;
    scanf("%c %d %d %d", &c, &a, &b, &x);
    if (c == 'M') {
      asq[i] = query(2, a, b, x);
      updm(2, a, b, x);
    } else {
      asq[i] = query(1, a, b, x);
      updm(1, a, b, x);
    }
  }

  buildget();
  for (int i = 2; i <= n; i++) {
//    cout << ar1[i].sc << ' ' << ar2[i].sc << endl;
    if (ar1[i].sc > 0 && ar1[i].sc <= q) {
      gr1[n + ar1[i].sc].pb(i);
//      cout << i << ' ' << ar1[i].sc << endl;
    }
    if (ar2[i].sc > 0 && ar2[i].sc <= q) {
      gr1[n + ar2[i].sc].pb(i);
//      cout << i << ' ' << ar2[i].sc << endl;
    }
  }
  int run = 1;
  while(run) {
    run = 0;
    for (int i = n + 1; i <= n + q; i++) {
      if (prr[i] == -1 && kuhn(i)) {
        run = 1;
      }
    }
    memset(used, 0, sizeof used);
  }
//  for (int i = 2; i <= n; i++) {
//    cout << i << ' ' << mt[i] - n << endl;
//  }
//  for (int i = 2; i <= n; i++) {
//    assert(prr[i] - n >= 1 && prr[i] - n <= q);
//  }
  for (int i = 2; i <= n; i++) {
    int val;
    if (mt[i] == -1) {
      if (ar1[i].fr != inf) {
        val = ar1[i].fr;
      } else if (ar2[i].fr != -1) {
        val = ar2[i].fr;
      } else {
        val = 1;
      }
    } else {
      val = asq[mt[i] - n].val;
    }
    printf("%d %d %d\n", i, pr[i], val);
  }
}
/*
5
1 2
1 3
3 4
3 5
4
m 2 4 1
M 4 5 2
M 2 3 5
m 2 3 4
*/

Compilation message

minmaxtree.cpp:188:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:191:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
minmaxtree.cpp:194:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &v, &u);
     ~~~~~^~~~~~~~~~~~~~~~~
minmaxtree.cpp:202:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
   ~~~~~^~~~~~~~~~
minmaxtree.cpp:206:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("\n");
     ~~~~~^~~~~~
minmaxtree.cpp:208:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%c %d %d %d", &c, &a, &b, &x);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 42744 KB Output is correct
2 Correct 38 ms 42744 KB Output is correct
3 Correct 40 ms 42816 KB Output is correct
4 Correct 46 ms 42816 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 59860 KB Output is correct
2 Correct 586 ms 59860 KB Output is correct
3 Correct 432 ms 59860 KB Output is correct
4 Correct 393 ms 60356 KB Output is correct
5 Correct 480 ms 60356 KB Output is correct
6 Correct 414 ms 60356 KB Output is correct
7 Correct 305 ms 60356 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 60356 KB Output is correct
2 Correct 298 ms 60356 KB Output is correct
3 Correct 220 ms 60356 KB Output is correct
4 Correct 204 ms 60356 KB Output is correct
5 Correct 299 ms 60356 KB Output is correct
6 Correct 292 ms 60356 KB Output is correct
7 Correct 263 ms 60356 KB Output is correct
8 Correct 345 ms 60356 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 42744 KB Output is correct
2 Correct 38 ms 42744 KB Output is correct
3 Correct 40 ms 42816 KB Output is correct
4 Correct 46 ms 42816 KB Output is correct
5 Correct 430 ms 59860 KB Output is correct
6 Correct 586 ms 59860 KB Output is correct
7 Correct 432 ms 59860 KB Output is correct
8 Correct 393 ms 60356 KB Output is correct
9 Correct 480 ms 60356 KB Output is correct
10 Correct 414 ms 60356 KB Output is correct
11 Correct 305 ms 60356 KB Output is correct
12 Correct 268 ms 60356 KB Output is correct
13 Correct 298 ms 60356 KB Output is correct
14 Correct 220 ms 60356 KB Output is correct
15 Correct 204 ms 60356 KB Output is correct
16 Correct 299 ms 60356 KB Output is correct
17 Correct 292 ms 60356 KB Output is correct
18 Correct 263 ms 60356 KB Output is correct
19 Correct 345 ms 60356 KB Output is correct
20 Correct 654 ms 60356 KB Output is correct
21 Correct 576 ms 60356 KB Output is correct
22 Correct 588 ms 60356 KB Output is correct
23 Correct 482 ms 60356 KB Output is correct
24 Correct 301 ms 60356 KB Output is correct
25 Correct 385 ms 60948 KB Output is correct
26 Correct 412 ms 60948 KB Output is correct
27 Correct 572 ms 60948 KB Output is correct
28 Correct 574 ms 60948 KB Output is correct
29 Correct 588 ms 60948 KB Output is correct
30 Correct 707 ms 60948 KB Output is correct
31 Correct 609 ms 60948 KB Output is correct
32 Correct 514 ms 60948 KB Output is correct
33 Correct 622 ms 60948 KB Output is correct
34 Correct 595 ms 60948 KB Output is correct
35 Correct 462 ms 60948 KB Output is correct