Submission #849882

#	Time	Username	Problem	Language	Result	Execution time	Memory
849882		1075508020060209tc	Vinjete (COI22_vinjete)	C++14	69 / 100	379 ms	138120 KiB

Main

#include<bits/stdc++.h>
using namespace std;
//#define int long long
int n;int m;int M;
struct SGTR{
int rl;int rr;
int l;int r;
int mn;
int mnfq;
int lz;
}tr[1000005];
vector<pair<int,int>>e[100005];//{v,eid}
int lar[100005];int rar[100005];
pair<int,int>rmp[2000006];
void pull(int nw){
if(tr[nw*2].mn<tr[nw*2+1].mn){
    tr[nw].mn=tr[nw*2].mn;
    tr[nw].mnfq=tr[nw*2].mnfq;
    return;
}
if(tr[nw*2+1].mn<tr[nw*2].mn){
    tr[nw].mn=tr[nw*2+1].mn;
    tr[nw].mnfq=tr[nw*2+1].mnfq;
    return;
}
tr[nw].mn=tr[nw*2].mn;
tr[nw].mnfq=tr[nw*2].mnfq+tr[nw*2+1].mnfq;
}

void buildtr(int nw,int l,int r){
tr[nw].l=l;tr[nw].r=r;
tr[nw].rl=rmp[l].first;tr[nw].rr=rmp[r].second;
tr[nw].mn=0;
tr[nw].lz=0;
if(l==r){
    tr[nw].mnfq=tr[nw].rr-tr[nw].rl+1;
    return;
}
int mi=(l+r)/2;
buildtr(nw*2,l,mi);buildtr(nw*2+1,mi+1,r);
pull(nw);
}

void psh(int nw){
tr[nw*2].mn+=tr[nw].lz;
tr[nw*2+1].mn+=tr[nw].lz;
tr[nw*2].lz+=tr[nw].lz;
tr[nw*2+1].lz+=tr[nw].lz;
tr[nw].lz=0;
}

void upd(int nw,int rl,int rr,int v){
if(tr[nw].rl>=rl&&tr[nw].rr<=rr){
    tr[nw].lz+=v;
    tr[nw].mn+=v;
   // cout<<"hehe";
    //cout<<nw<<" "<<tr[nw].rl<<" "<<tr[nw].rr<<" "<<tr[nw].mn<<" "<<tr[nw].mnfq<<" "<<tr[nw].lz<<endl;
    return;
}
if(tr[nw].rl>rr||tr[nw].rr<rl){return;}
psh(nw);
upd(nw*2,rl,rr,v);upd(nw*2+1,rl,rr,v);
pull(nw);
}
int totlen;
void lisanhua(){
set<pair<int,int>>st;
set<int>stt;
for(int i=1;i<=n-1;i++){
    st.insert({lar[i],lar[i]});
    st.insert({rar[i],rar[i]});
    stt.insert(lar[i]);
    stt.insert(rar[i]);
}
for(auto it=stt.begin();it!=stt.end();it++){
    if(next(it)!=stt.end()){
        int v=(*it);
        int vv=(*next(it));
        if(vv-v>=2){
            st.insert({v+1,vv-1});
        }
    }
}
m=0;
for(auto it=st.begin();it!=st.end();it++){
    int l=(*it).first;int r=(*it).second;
    rmp[++m]={l,r};
   // cout<<l<<" "<<r<<endl;
}
totlen=rmp[m].second-rmp[1].first+1;
}
int fans[200005];

void dfs(int nw,int pa){
if(tr[1].mn==0){
    fans[nw]=totlen-tr[1].mnfq;
}else{
    fans[nw]=totlen;
}
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i].first;
    if(v==pa){continue;}
    int id=e[nw][i].second;
    upd(1,lar[id],rar[id],1);
    dfs(v,nw);
    upd(1,lar[id],rar[id],-1);
}


}


signed main(){
cin>>n>>m;
for(int i=1;i<=n-1;i++){
    int a;int b;
    cin>>a>>b>>lar[i]>>rar[i];
    e[a].push_back({b,i});
    e[b].push_back({a,i});
}
lisanhua();
buildtr(1,1,m);
/*
upd(1,1,4,1);
cout<<tr[1].mnfq<<"\n";
for(int nw=1;nw<=24;nw++){
    cout<<nw<<" "<<tr[nw].rl<<" "<<tr[nw].rr<<" "<<tr[nw].mn<<" "<<tr[nw].mnfq<<" "<<tr[nw].lz<<endl;
}

upd(1,2,3,1);
cout<<tr[1].mnfq<<"\n";

for(int nw=1;nw<=24;nw++){
    cout<<nw<<" "<<tr[nw].rl<<" "<<tr[nw].rr<<" "<<tr[nw].mn<<" "<<tr[nw].mnfq<<" "<<tr[nw].lz<<endl;
}

return 0;
cout<<endl<<endl;*/
dfs(1,0);
for(int i=2;i<=n;i++){
    cout<<fans[i]<<"\n";
}

}

Compilation message (stderr)

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:100:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~

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