제출 #747083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
747083		MilosMilutinovic	Vinjete (COI22_vinjete)	C++14	100 / 100	697 ms	152852 KiB

Main

/**
 *    author:  wxhtzdy
 *    created: 20.12.2022 14:09:07
**/
#include <bits/stdc++.h>

using namespace std;

const int M = 8e6;

int root, tsz, ls[M], rs[M], mn[M], cnt[M], add[M];

int make_node(int l, int r) {
  int node = ++tsz;
  cnt[node] = max(0, r - l + 1);
  if (l > r) {
    mn[node] = 1e6;
  }
  return node;
}

void push(int x, int l, int r) {
  if (add[x] == 0) {
    return;
  }
  int mid = l + r >> 1;
  if (!ls[x]) {
    ls[x] = make_node(l, mid);
  }
  if (!rs[x]) {
    rs[x] = make_node(mid + 1, r);
  }
  mn[ls[x]] += add[x];
  mn[rs[x]] += add[x];
  add[ls[x]] += add[x];
  add[rs[x]] += add[x];
  add[x] = 0;
}

void pull(int x) {
  mn[x] = min(mn[ls[x]], mn[rs[x]]);
  cnt[x] = (mn[ls[x]] == mn[x] ? cnt[ls[x]] : 0) + (mn[rs[x]] == mn[x] ? cnt[rs[x]] : 0);
}

void modify(int x, int l, int r, int ll, int rr, int v) {
  assert(x > 0);
  if (l > r || l > rr || r < ll) {
    return;
  }
  if (ll <= l && r <= rr) {
    mn[x] += v;
    add[x] += v;
    push(x, l, r);
    return;
  }
  push(x, l, r);
  int mid = l + r >> 1;
  if (!ls[x]) {
    ls[x] = make_node(l, mid);
  }
  modify(ls[x], l, mid, ll, rr, v);
  if (!rs[x]) {
    rs[x] = make_node(mid + 1, r);
  }
  modify(rs[x], mid + 1, r, ll, rr, v);
  pull(x);
}


int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m;
  cin >> n >> m;
  vector<vector<array<int, 3>>> g(n);
  for (int i = 1; i < n; i++) {
    int x, y, l, r;
    cin >> x >> y >> l >> r;
    --x; --y;
    g[x].push_back({y, l, r});
    g[y].push_back({x, l, r});
  }
  root = make_node(1, m);
  vector<int> ans(n);
  function<void(int, int)> Dfs = [&](int v, int pv) {
    ans[v] = (mn[root] == 0 ? m - cnt[root] : m);
    for (auto p : g[v]) {
      int u = p[0];
      int l = p[1];
      int r = p[2];
      if (u == pv) {
        continue;
      }
      modify(root, 1, m, l, r, +1);
      Dfs(u, v);
      modify(root, 1, m, l, r, -1);
    }
  };
  Dfs(0, 0);
  for (int i = 1; i < n; i++) {
    cout << ans[i] << '\n';
  }                                                               
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void push(int, int, int)':
Main.cpp:26:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'void modify(int, int, int, int, int, int)':
Main.cpp:57:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |   int mid = l + r >> 1;
      |             ~~^~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31