Submission #1019014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019014		MarwenElarbi	Vinjete (COI22_vinjete)	C++17	100 / 100	473 ms	150876 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define pb push_back
#define se second
#define fi first
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int nax=1e5+5;
struct edge{
    int x,l,r;
};
vector<edge> adj[nax];
struct node{
    int ans,lazy,cnt,tl,tr,l,r;
    node () : ans(0), lazy(0),cnt (0), l(-1), r(-1) {}
};
node segtree[nax*50];
int cnt=1;
int res[nax];
void push_lazy(int pos){
    if(segtree[pos].lazy==0) return;
    int mid=(segtree[pos].tl+segtree[pos].tr)/2;
    if(segtree[pos].l==-1){
        segtree[pos].l=cnt++;
        segtree[segtree[pos].l].tl=segtree[pos].tl;
        segtree[segtree[pos].l].tr=mid;
    }
    if(segtree[pos].r==-1){
        segtree[pos].r=cnt++;
        segtree[segtree[pos].r].tl=mid+1;
        segtree[segtree[pos].r].tr=segtree[pos].tr;
    }
    segtree[pos].lazy=0;
}
void update(int pos,int l,int r,int value){
    push_lazy(pos);
    //cout <<l<<" "<<r<<" "<<pos<<endl;
    if(l==segtree[pos].tl&&r==segtree[pos].tr){
        segtree[pos].cnt+=value;
        if(segtree[pos].cnt) segtree[pos].ans=(segtree[pos].tr-segtree[pos].tl+1);
        else segtree[pos].ans=segtree[segtree[pos].l].ans+segtree[segtree[pos].r].ans;
        push_lazy(pos);
        return;
    }
    int mid=(segtree[pos].tl+segtree[pos].tr)/2;
    //cout <<segtree[pos].tl<<" "<<segtree[pos].tr<<endl;
    if(segtree[pos].l==-1){
        segtree[pos].l=cnt++;
        segtree[segtree[pos].l].tl=segtree[pos].tl;
        segtree[segtree[pos].l].tr=mid;
    }
    if(segtree[pos].r==-1){
        segtree[pos].r=cnt++;
        segtree[segtree[pos].r].tl=mid+1;
        segtree[segtree[pos].r].tr=segtree[pos].tr;
    }
    if(l>mid) update(segtree[pos].r,l,r,value);
    else if(r<=mid) update(segtree[pos].l,l,r,value);
    else{
        update(segtree[pos].l,l,mid,value);
        update(segtree[pos].r,mid+1,r,value);
    }
    push_lazy(segtree[pos].l);
    push_lazy(segtree[pos].r);
    //cout <<segtree[pos].tl<<" "<<segtree[pos].tr<<" "<<segtree[segtree[pos].l].ans<<" "<<segtree[segtree[pos].r].cnt<<endl;
    segtree[pos].ans=(segtree[pos].cnt ? segtree[pos].tr-segtree[pos].tl+1 : segtree[segtree[pos].l].ans+segtree[segtree[pos].r].ans);
}
void dfs(int x,int p){
    res[x]=segtree[0].ans;
    for(auto u:adj[x]){
        if(p==u.x) continue;
        update(0,u.l,u.r,1);
        dfs(u.x,x);
        update(0,u.l,u.r,-1);
    }
    return;
}
int main() {
    optimise;
    int n,m;
    cin>>n>>m;
    for (int i = 0; i < n-1; ++i)
    {
        int x,y,l,r;
        cin>>x>>y>>l>>r;
        x--;y--;
        adj[x].pb({y,l,r});
        adj[y].pb({x,l,r});
    }
    segtree[0].tl=0;
    segtree[0].tr=1e9;
    dfs(0,-1);
    for (int i = 1; i < n; ++i)
    {
        cout <<res[i]<<endl;
    }
}

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