Submission #990629

#	Time	Username	Problem	Language	Result	Execution time	Memory
990629		alexdd	Vinjete (COI22_vinjete)	C++17	100 / 100	395 ms	182680 KiB

Main

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<pair<int,pair<int,int>>> con[100005];
pair<int,int> combine(pair<int,int> x, pair<int,int> y)
{
    if(x.first < y.first)
        return x;
    if(x.first > y.first)
        return y;
    return {x.first,x.second+y.second};
}
struct node
{
    pair<int,int> mnm;
    int lazy,tole,tori;
};
node emp = {{0,0},0,0,0};
vector<node> aint;
void baga(int nod, int val)
{
    aint[nod].lazy+=val;
    aint[nod].mnm.first+=val;
}
void propagate(int nod)
{
    if(!aint[nod].lazy)
        return;
    baga(aint[nod].tole,aint[nod].lazy);
    baga(aint[nod].tori,aint[nod].lazy);
    aint[nod].lazy=0;
}
void upd(int nod, int st, int dr, int le, int ri, int newv)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        baga(nod,newv);
        return;
    }
    int mij=(st+dr)/2;
    if(aint[nod].tole==0)
    {
        aint[nod].tole = aint.size();
        aint.push_back({{0,mij-st+1},0,0,0});
    }
    if(aint[nod].tori==0)
    {
        aint[nod].tori = aint.size();
        aint.push_back({{0,dr-mij},0,0,0});
    }
    propagate(nod);
    upd(aint[nod].tole,st,mij,le,min(mij,ri),newv);
    upd(aint[nod].tori,mij+1,dr,max(mij+1,le),ri,newv);
    aint[nod].mnm = combine(aint[aint[nod].tole].mnm, aint[aint[nod].tori].mnm);
}
int rez[100005];
void dfs(int nod, int par, pair<int,int> r)
{
    upd(0,1,m,r.first,r.second,1);
    if(aint[0].mnm.first==0) rez[nod] = m - aint[0].mnm.second;
    else rez[nod] = m;
    for(auto x:con[nod])
    {
        if(x.first!=par)
        {
            dfs(x.first,nod,x.second);
        }
    }
    upd(0,1,m,r.first,r.second,-1);
}
signed main()
{
    cin>>n>>m;
    int u,v,a,b;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v>>a>>b;
        con[u].push_back({v,{a,b}});
        con[v].push_back({u,{a,b}});
    }
    aint.push_back({{0,m},0,0,0});
    dfs(1,0,{1,0});
    for(int i=2;i<=n;i++)
        cout<<rez[i]<<"\n";
    return 0;
}

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