Submission #1146605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146605		Moonn	Vinjete (COI22_vinjete)	C++20	0 / 100	46 ms	118156 KiB

Main

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define AI ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
random_device rd;
mt19937_64 gen(rd());
uniform_int_distribution<uint64_t>distrib(1,UINT_MAX);
const ll sz=5e6;
ll nw=1;
struct node
{
    ll l;
    ll r;
    ll sum;
    node(): l(0),r(0),sum(0){};
};
struct vertex
{
    ll b;
    ll ql;
    ll qr;
};
node Nodes[sz];
vector<vector<vertex>>v;
vector<vertex>pa;
queue<ll>sr;
map<ll,ll>ok;//orginal->kod
map<ll,ll>ko;
void dfs(ll x,ll p=-1)
{
    sr.push(x);
    for(ll i=0;i<v[x].size();i++)
    {
        if(v[x][i].b!=p)
        {
            pa[v[x][i].b]=v[x][i];
            pa[v[x][i].b].b=x;
            dfs(v[x][i].b,x);
        }
    }
}
ll build(ll l,ll r)
{
    if(l==r)
    return nw++;
    ll mid=(l+r)/2;
    ll nww=nw++;
    Nodes[nww].l=build(l,mid);
    Nodes[nww].r=build(mid+1,r);
    return nww;
}
ll upd(ll l,ll r,ll xl,ll xr,ll pos)
{
    if(l==r)
    {
        Nodes[nw].sum=1;
        return nw++;
    }
    if(ko[r]-ko[l]+1==Nodes[pos].sum)
    return pos;
    if(xl<=l and r<=xr)
    {
        Nodes[nw].sum=ko[r]-ko[l]+1;
        return nw++;
    }
    ll mid=(l+r)/2;
    ll nww=nw++;
    if(!(l>xr or xl>mid))
    Nodes[nww].l=upd(l,mid,xl,xr,Nodes[pos].l);
    else
    Nodes[nww].l=Nodes[pos].l;
    if(!(mid+1>xr or xl>r))
    Nodes[nww].r=upd(mid+1,r,xl,xr,Nodes[pos].r);
    else
    Nodes[nww].r=Nodes[pos].r;
    Nodes[nww].sum=(Nodes[Nodes[nww].l].sum+Nodes[Nodes[nww].r].sum);
    return nww;
}
void print(ll v,ll l,ll r)
{
    cout<<Nodes[v].sum<<' '<<l<<' '<<r<<endl;
    if(l==r)
    return;
    else
    {
        ll m=(l+r)/2;
        print(Nodes[v].l,l,m);
        print(Nodes[v].r,m+1,r);
    }

}
int main()
{
    AI
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ll n,m,i,t,x,y,l,r;
    cin>>n>>m;
    v.resize(n+1);
    pa.resize(n+1);
    vector<ll>co;
    vector<ll>ver(n+1,0);
    for(i=1;i<n;i++)
    {
        cin>>x>>y>>l>>r;
        co.push_back(l);
        co.push_back(r);
        vertex ne;
        ne.b=y;
        ne.ql=l;
        ne.qr=r;
        v[x].push_back(ne);
        ne.b=x;
        v[y].push_back(ne);
    }
    dfs(1);
    sort(co.begin(),co.end());
    t=1;
    for(i=0;i<co.size();i++)
    {
        if(ok[co[i]])
        continue;
        ko[t]=co[i];
        ok[co[i]]=t++;
    }
    ver[1]=build(1,t);
    sr.pop();
   // cout<<sr.size()<<endl;
    while(sr.size())
    {
        i=sr.front();
        sr.pop();
        x=pa[i].b;
        l=pa[i].ql;
        r=pa[i].qr;
        l=ok[l];
        r=ok[r];
        ver[i]=(upd(1,t-1,l,r,ver[x]));
      //  cout<<i<<' '<<x<<' '<<l<<' '<<r<<endl;
    }
    for(i=2;i<=n;i++)
    cout<<Nodes[ver[i]].sum<<endl;
}

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