oj.uz

Submission #521969

# Submission time Handle Problem Language Result Execution time Memory
521969 2022-02-03T14:23:38 Z cadmiumsky Min-max tree (BOI18_minmaxtree) C++14
100 / 100
 431 ms 58752 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int nmax = 7e4 + 5;
 
const int inf = 1e9 + 1;
#define pushb push_back
pair<int,int> vec[nmax];
int ptrx = 0;
struct CuplajDeFraieri {
  struct edg {
    int u, v, cap, flow = 0;
    edg(int c, int a, int b) : u(c), v(a), cap(b) {;}
  };
  vector<int> ptr;
  vector<int> level;
  vector<edg> edge;
  vector<vector<int > > g;
  int n, s, t;
  CuplajDeFraieri(int a, int b, int c) : n(a), s(b), t(c) {
    ptr.resize(n + 1);
    level.resize(n + 1);
    g.resize(n + 1);
  }
  void push(int u, int v, int cap) {
    g[u].push_back(edge.size());
    edge.pushb(edg(u, v, cap));
    g[v].push_back(edge.size());
    edge.pushb(edg(v, u, 0));
  }
  queue<int> que;
  bool bfs() {
    if(que.empty())
      return 0;
    int node = que.front();
    que.pop();
    if(node == t)
      return 1;
    for(auto x : g[node]) {
      if(level[edge[x].v] == -1 && edge[x].flow < edge[x].cap ) {
        que.push(edge[x].v);
        level[edge[x].v] = level[node] + 1;
      }
    }
    return bfs();
  }
  int dfs(int node, int mn = inf) {
    if(node == t)
      return mn;
    for(int &i = ptr[node]; i < g[node].size(); i++) {
      int x = g[node][i];
      if(edge[x].flow >= edge[x].cap || level[edge[x].v] != level[node] + 1)
        continue;
      int temp = dfs(edge[x].v, min(edge[x].cap - edge[x].flow, mn));
      if(temp == 0)
        continue;
      edge[x].flow += temp;
      edge[x ^ 1].flow -= temp;
      return temp;
    }
    return 0;
  }
  void get() {
    while(1) {
      fill(level.begin(), level.end(), -1);
      level[s] = 0;
      que = queue<int>();
      que.push(s);
      if(!bfs())
        break;
      fill(ptr.begin(), ptr.end(), 0);
      while(dfs(s));
    }
    for(auto x : edge) {
      if(x.u == s)
        continue;
      if(x.v == t)
        continue;
      if(x.cap == 0)
        continue;
      if(x.flow == 1)
        vec[ptrx++] = {x.u, x.v};
    }
    return;
  }
};
 
struct edg {
  int u, other, mn, mx;
};
edg edge[nmax];
int pedge[nmax];
vector<int> g[nmax];
 
 
namespace LCA {
  int dpmn[nmax][17];
  int dpmx[nmax][17];
  int father[nmax][17];
  int pin[nmax], pout[nmax];
  int inp = 0;
  void init(int node, int f) {
    //cout << node << ' ' <<f << '\n';
    father[node][0] = f;
    dpmn[node][0] = -inf;
    dpmx[node][0] = inf;
    for(int i = 1; i < 17; i++) {
      father[node][i] = father[father[node][i - 1]][i - 1];
      dpmn[node][i] = -inf;
      dpmx[node][i] = inf;
    }
    int c;
    pin[node] = inp++;
    for(auto x : g[node]) {
      c = edge[x].other ^ node;
      if(c == f) {
        pedge[node] = x;
        continue;
      }
      init(c, node);
    }
    pout[node] = inp - 1;
    return;
  }
  inline bool isanc(int f, int node) {
    return pin[f] <= pin[node] && pout[node] <= pout[f];
  }
  void add(char ch, int x, int y, int val) {
    //cout << "! " << x + 1 << ' ' << y + 1 <<  ' '<< val << '\n';
    for(int i = 16; i >= 0; i--) {
      if(!isanc(father[x][i], y)) {
        //cout << x + 1 << ' '<< father[x][i] + 1 << ' '<< val << '\n';
        (ch == 'M'? dpmx[x][i] = min(dpmx[x][i], val) : dpmn[x][i] = max(dpmn[x][i], val));
        x = father[x][i];
      }
    }
    if(!isanc(x, y)) {
        //cout << x + 1 << ' '<< father[x][0] + 1 << ' '<< val << '\n';
      (ch == 'M'? dpmx[x][0] = min(dpmx[x][0], val) : dpmn[x][0] = max(dpmn[x][0], val));
    }
    for(int i = 16; i >= 0; i--) {
       if(!isanc(father[y][i], x)) {
        //cout << y + 1 << ' '<< father[y][i] + 1 << ' '<< val << '\n';
        (ch == 'M'? dpmx[y][i] = min(dpmx[y][i], val) : dpmn[y][i] = max(dpmn[y][i], val));
       y = father[y][i];
      }
    }
    if(!isanc(y, x))  {
        //cout << y + 1 << ' '<< father[y][0] + 1 << ' '<< val << '\n';
      (ch == 'M'? dpmx[y][0] = min(dpmx[y][0], val) : dpmn[y][0] = max(dpmn[y][0], val));
    }
    return;
  }
  void mkdp(int node, int f) {
   for(auto x : g[node]) {
      int c = edge[x].other ^ node;
      if(c == f) 
        continue;
      mkdp(c, node);
    }
    for(int i = 16; i > 0; i--) {
      dpmx[node][i - 1] = min(dpmx[node][i], dpmx[node][i - 1]);  
      dpmx[father[node][i - 1]][i - 1] = min(dpmx[node][i], dpmx[father[node][i - 1]][i - 1]);  
      dpmn[node][i - 1] = max(dpmn[node][i], dpmn[node][i - 1]);  
      dpmn[father[node][i - 1]][i - 1] = max(dpmn[node][i], dpmn[father[node][i - 1]][i - 1]);  
    }
    //cout << "> " << node + 1 << ' ' << dpmx[node][0] << ' '<<dpmn[node][0] << '\n';
   if(node != f) {
      edge[pedge[node]].mn = dpmn[node][0];
      edge[pedge[node]].mx = dpmx[node][0];
    }
    return;
  }
};
#define norm sad
map<int,int> norm;
map<int,int> inv;
 
int main() {
  int n;
  cin >> n;
  for(int i = 1, x, y; i < n; i++) {
    cin >> x >> y;
    --x;
    --y;
    g[x].push_back(i);
    g[y].push_back(i);
    edge[i] = edg{x, x ^ y, -inf, inf};
  }
  LCA::init(0,0);
  int q;
  cin >> q;
  char ch;
  for(int i = 0, x, y, w; i < q; i++) {
    cin >> ch >> x>> y >> w;
    --x;
    --y;
    norm[w];
    LCA::add(ch, x, y, w);
  }
  LCA::mkdp(0,0);
  int normax = n + 2;
  for(auto &x : norm) {
    x.second = normax;
    inv[x.second] = x.first;
    normax++;
  }
  int cnt = 2;
  const int S = 0, T = 1;
  CuplajDeFraieri flux(normax + 5, S, T);
  for(int i = n + 2; i < normax; i++)
    flux.push(S, i, 1);
  for(int i = 1; i < n; i++) {
    auto x = edge[i];
    if(x.mn == x.mx) 
      x.mx = inf;
    if(x.mn != -inf)
      flux.push(norm[x.mn], cnt, 1);
    if(x.mx != inf)
      flux.push(norm[x.mx], cnt, 1);
    flux.push(cnt, T, 1);
    cnt++;
  }
  flux.get();
  for(int i = 0; i < ptrx; i++) {
    auto x = vec[i];
    //cout << x.second - 2 << ' ' << inv[x.first] << '\n';
    edge[x.second - 1].mx = inv[x.first];
  }
  for(int i = 1; i < n; i++) {
    auto x = edge[i];
    cout << x.u + 1 << ' ' << (x.other ^ x.u) + 1 << ' ' << min(x.mx, inf - 1) << '\n';
  }
}

Compilation message

minmaxtree.cpp: In member function 'int CuplajDeFraieri::dfs(int, int)':
minmaxtree.cpp:50:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int &i = ptr[node]; i < g[node].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 1 ms 1952 KB Output is correct
3 Correct 1 ms 1996 KB Output is correct
4 Correct 1 ms 1948 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 47192 KB Output is correct
2 Correct 322 ms 46092 KB Output is correct
3 Correct 331 ms 45564 KB Output is correct
4 Correct 384 ms 50276 KB Output is correct
5 Correct 334 ms 46044 KB Output is correct
6 Correct 351 ms 47500 KB Output is correct
7 Correct 357 ms 46368 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 36144 KB Output is correct
2 Correct 206 ms 37768 KB Output is correct
3 Correct 228 ms 37036 KB Output is correct
4 Correct 197 ms 38316 KB Output is correct
5 Correct 213 ms 38276 KB Output is correct
6 Correct 224 ms 38900 KB Output is correct
7 Correct 213 ms 38220 KB Output is correct
8 Correct 217 ms 38172 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 1 ms 1952 KB Output is correct
3 Correct 1 ms 1996 KB Output is correct
4 Correct 1 ms 1948 KB Output is correct
5 Correct 381 ms 47192 KB Output is correct
6 Correct 322 ms 46092 KB Output is correct
7 Correct 331 ms 45564 KB Output is correct
8 Correct 384 ms 50276 KB Output is correct
9 Correct 334 ms 46044 KB Output is correct
10 Correct 351 ms 47500 KB Output is correct
11 Correct 357 ms 46368 KB Output is correct
12 Correct 188 ms 36144 KB Output is correct
13 Correct 206 ms 37768 KB Output is correct
14 Correct 228 ms 37036 KB Output is correct
15 Correct 197 ms 38316 KB Output is correct
16 Correct 213 ms 38276 KB Output is correct
17 Correct 224 ms 38900 KB Output is correct
18 Correct 213 ms 38220 KB Output is correct
19 Correct 217 ms 38172 KB Output is correct
20 Correct 375 ms 47356 KB Output is correct
21 Correct 305 ms 43680 KB Output is correct
22 Correct 294 ms 43880 KB Output is correct
23 Correct 321 ms 44304 KB Output is correct
24 Correct 425 ms 57232 KB Output is correct
25 Correct 431 ms 58752 KB Output is correct
26 Correct 381 ms 57392 KB Output is correct
27 Correct 429 ms 56480 KB Output is correct
28 Correct 381 ms 48796 KB Output is correct
29 Correct 394 ms 48824 KB Output is correct
30 Correct 345 ms 45872 KB Output is correct
31 Correct 351 ms 46192 KB Output is correct
32 Correct 375 ms 48416 KB Output is correct
33 Correct 341 ms 46660 KB Output is correct
34 Correct 342 ms 46660 KB Output is correct
35 Correct 330 ms 45704 KB Output is correct