Submission #881009

#	Time	Username	Problem	Language	Result	Execution time	Memory
881009		epicci23	Vinjete (COI22_vinjete)	C++17	100 / 100	911 ms	441840 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl '\n'
#define all(x) ((x).begin(),(x).end())
#define sz(x) ((int)(x).size())

const int N = 1e5 + 5;

struct Node{
  Node* lc;Node* rc;
  int lf,rg;
  int mini,cnt,lazy;
  Node(int ll,int rr){
    lc=rc=NULL;
    lazy=mini=0;
    lf=ll; rg=rr;
    cnt=rr-ll+1;
  }
};

Node* root;

void push(Node *rt){
  if(rt==NULL) return;
  int hl = rt->lf,hr = rt->rg;
  int hm = (hl+hr)/2;
  int u = rt->lazy;
  rt->mini+=u; rt->lazy=0;

  if(rt->lc==NULL)rt->lc=new Node(hl,hm);
  rt->lc->lazy+=u;
  
  if(rt->rc==NULL) rt->rc=new Node(hm+1,hr);
  rt->rc->lazy+=u;

  return;
}

void update(Node* rt,int l,int r,int gl,int gr,int u){
  push(rt);
  if(rt==NULL) return;
  if(r<gl || l>gr) return;
  if(l>=gl && r<=gr){
    rt->lazy+=u;
    push(rt); 
    return;
  }
  int mi = (l+r)/2;
  update(rt->lc,l,mi,gl,gr,u);
  update(rt->rc,mi+1,r,gl,gr,u);
  rt->mini=min(rt->lc->mini,rt->rc->mini);
  rt->cnt=0;
  if(rt->mini==rt->lc->mini) rt->cnt+=rt->lc->cnt;
  if(rt->mini==rt->rc->mini) rt->cnt+=rt->rc->cnt;
}

vector<array<int,3>> v[N];
int ans[N],n,m;

void dfs(int c,int p){
  push(root);

  if(root->mini==0) ans[c] = m - root->cnt;
  else ans[c]=m;

  for(auto x:v[c]){
    if(x[0]==p) continue;
    update(root,1,m,x[1],x[2],1);
    dfs(x[0],c);
    update(root,1,m,x[1],x[2],-1);
  }
}

void solve(){
  
  cin >> n >> m;
  root=new Node(1,m);
  for(int i=1;i<n;i++){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    v[a].pb({b,c,d});
    v[b].pb({a,c,d});
  }
  
  dfs(1,0);

  for(int i=2;i<=n;i++) cout << ans[i] << endl;
}

int32_t main(){
  ios::sync_with_stdio(0);cin.tie(0);
  int t=1;//cin >> t;
  while(t--) solve();
}

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