Submission #1210229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210229		bakhtiyarn	Vinjete (COI22_vinjete)	C++20	69 / 100	1694 ms	529284 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 8000000;

const int N2 = 1e5+5;

vector<array<int, 3>> g[N2];
int ans[N2];

int n, M;
int nxt = 1;

int L[N], R[N], sg[N], lz[N];

vector<array<int, 2>> chsg;
vector<array<int, 2>> chlz;

unordered_map<int, int> usedsg, usedlz;

void push(int u, int l, int r, int U){
  if(lz[u]) {
    if(!usedsg[u]) usedsg[u] = 1, chsg.push_back({u, sg[u]});
    sg[u] = r-l+1;
  }
  
  if(l != r){
    if(L[u]){
      if(!usedlz[L[u]]) usedlz[L[u]] = 1, chlz.push_back({L[u], lz[L[u]]});
      lz[L[u]] += lz[u];
    }
    
    if(R[u]){
      if(!usedlz[R[u]]) usedlz[R[u]] = 1, chlz.push_back({R[u], lz[R[u]]});
      lz[R[u]] += lz[u];
    }
  }
}

void update(int u, int l, int r, int x, int y, int U){
  push(u, l, r, U);
  if(y < l or x > r) return;
  if(x <= l and y >= r){
    if(!usedlz[u]) usedlz[u] = 1, chlz.push_back({u, lz[u]});
    lz[u]++;
    push(u, l, r, U);
    return;
  }
  
  ///
    int m = (l+r)/2;
    
    bool sol = true;
    if(y < l or x > m) sol = false;
    if(sol){
      if(!L[u]) L[u] = ++nxt;
      push(u, l, r, U);
      update(L[u], l, m, x, y, U);
    } else {
      if(L[u]){
        push(L[u], l, m, U);
      }
    }
    
    bool sag = true;
    if(y < m+1 or x > r) sag = false;
    if(sag){
      if(!R[u]) R[u] = ++nxt;
      push(u, l, r, U);
      update(R[u], m+1, r, x, y, U);
    } else {
      if(R[u]){
        push(R[u], m+1, r, U);
      }
    }
  ///
  
  if(!usedsg[u]) usedsg[u] = 1, chsg.push_back({u, sg[u]});
  sg[u] = sg[L[u]] + sg[R[u]];
  if(lz[u]) sg[u] = r-l+1;
}

void dfs(int u, int p, int li, int ri){
  usedlz.clear(); usedsg.clear();
  chlz.clear(); chsg.clear();
  
  update(1, 1, M, li, ri, u);
  ans[u] = sg[1];
  
  vector<array<int, 2>> chsg2 = chsg;
  vector<array<int, 2>> chlz2 = chlz;
  
  for(auto [to, lj, rj]: g[u]){
    if(to == p) continue;
    dfs(to, u, lj, rj);
  }
  
  for(auto [node, ans]: chsg2) sg[node] = ans;
  for(auto [node, ans]: chlz2) lz[node] = ans;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  
  cin >> n >> M;
  for(int i=1; i<n; i++){
    int x, y, li, ri; cin >> x >> y >> li >> ri;
    g[x].push_back({y, li, ri});
    g[y].push_back({x, li, ri});
  }
  
  dfs(1, -1, 0, 0);
  
  for(int i=2; i<=n; i++) cout << ans[i] << '\n';
}

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