Submission #521969

#	Time	Username	Problem	Language	Result	Execution time	Memory
521969		cadmiumsky	Min-max tree (BOI18_minmaxtree)	C++14	100 / 100	431 ms	58752 KiB

minmaxtree

#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 (stderr)

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 / 7
• Subtask 2: 22 / 22
• Subtask 3: 29 / 29
• Subtask 4: 42 / 42