oj.uz

Submission #1018986

# Submission time Handle Problem Language Result Execution time Memory
1018986 2024-07-10T11:32:59 Z MarwenElarbi Vinjete (COI22_vinjete) C++17
0 / 100
 45 ms 85336 KB 
#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*30];
int cnt=1;
int res[nax];
void push_lazy(int pos){
    if(segtree[pos].lazy==0) return;
    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;
    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[segtree[pos].l].lazy+=segtree[pos].lazy;
    segtree[segtree[pos].r].lazy+=segtree[pos].lazy;
    segtree[segtree[pos].l].cnt+=segtree[pos].lazy;
    segtree[segtree[pos].r].cnt+=segtree[pos].lazy;
    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].lazy+=value;
        segtree[pos].cnt+=value;
        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);
    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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 85084 KB Output is correct
2 Correct 30 ms 85084 KB Output is correct
3 Correct 45 ms 85168 KB Output is correct
4 Correct 34 ms 85072 KB Output is correct
5 Correct 30 ms 85084 KB Output is correct
6 Correct 30 ms 85172 KB Output is correct
7 Correct 40 ms 85148 KB Output is correct
8 Correct 29 ms 85076 KB Output is correct
9 Incorrect 32 ms 85336 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 85084 KB Output is correct
2 Correct 30 ms 85084 KB Output is correct
3 Correct 45 ms 85168 KB Output is correct
4 Correct 34 ms 85072 KB Output is correct
5 Correct 30 ms 85084 KB Output is correct
6 Correct 30 ms 85172 KB Output is correct
7 Correct 40 ms 85148 KB Output is correct
8 Correct 29 ms 85076 KB Output is correct
9 Incorrect 32 ms 85336 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 85084 KB Output is correct
2 Correct 30 ms 85084 KB Output is correct
3 Correct 45 ms 85168 KB Output is correct
4 Correct 34 ms 85072 KB Output is correct
5 Correct 30 ms 85084 KB Output is correct
6 Correct 30 ms 85172 KB Output is correct
7 Correct 40 ms 85148 KB Output is correct
8 Correct 29 ms 85076 KB Output is correct
9 Incorrect 32 ms 85336 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 85084 KB Output is correct
2 Correct 30 ms 85084 KB Output is correct
3 Correct 45 ms 85168 KB Output is correct
4 Correct 34 ms 85072 KB Output is correct
5 Correct 30 ms 85084 KB Output is correct
6 Correct 30 ms 85172 KB Output is correct
7 Correct 40 ms 85148 KB Output is correct
8 Correct 29 ms 85076 KB Output is correct
9 Incorrect 32 ms 85336 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 85084 KB Output is correct
2 Correct 30 ms 85084 KB Output is correct
3 Correct 45 ms 85168 KB Output is correct
4 Correct 34 ms 85072 KB Output is correct
5 Correct 30 ms 85084 KB Output is correct
6 Correct 30 ms 85172 KB Output is correct
7 Correct 40 ms 85148 KB Output is correct
8 Correct 29 ms 85076 KB Output is correct
9 Incorrect 32 ms 85336 KB Output isn't correct
10 Halted 0 ms 0 KB -