Submission #83143

#	Time	Username	Problem	Language	Result	Execution time	Memory
83143		Bodo171	Construction of Highway (JOI18_construction)	C++14	100 / 100	373 ms	70636 KiB

construction

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
const int nmax=100005;
map<int,int> norm;
vector<int> v[nmax];
vector< pair<int,int> > l[nmax];
pair<int,int> vv[2*nmax];
long long aib[nmax];
int p[nmax],w[nmax],tt[nmax],lev[nmax],c[nmax],a[nmax],b[nmax],x[nmax];
int n,i,j,paths,nr,in,val;
long long ans;
void dfs(int x)
{
    int nod,big=0;
    w[x]=1;
    for(int i=0;i<v[x].size();i++)
    {
        nod=v[x][i];lev[nod]=lev[x]+1;
        dfs(nod);
        w[x]+=w[nod];
        if(w[nod]>w[big])
            big=nod;
    }
    if(!big) p[x]=++paths;
    else p[x]=p[big];
    for(int i=0;i<v[x].size();i++)
        if(v[x][i]!=big)
    {
        tt[p[v[x][i]]]=x;
    }
}
int get(int wh,int x)
{
    int ret=0;
    for(int p=16;p>=0;p--)
        if(ret+(1<<p)<l[wh].size()&&lev[l[wh][ret+(1<<p)].first]>=lev[x])
           ret+=(1<<p);
    ret++;
    return ret;
}
inline int lbit(int x)
{
    return ((x^(x-1))&x);
}
void update(int poz,long long val)
{
    for(int idx=poz;idx<=n;idx+=lbit(idx))
        aib[idx]+=val;
}
long long compute(int poz)
{
    long long ret=0;
    for(int idx=poz;idx>0;idx-=lbit(idx))
        ret+=1LL*aib[idx];
    return ret;
}
void ffffffffft(int x)
{
    int wh;
    nr=0;
    while(x!=0)
    {
        in=get(p[x],x);
        wh=p[x];
        vv[++nr]={lev[x],l[wh][in-1].second};
        for(i=in;i<l[wh].size();i++)
            vv[++nr]={lev[l[wh][i].first],l[wh][i].second};
        x=tt[p[x]];
    }
    vv[nr+1]={0,0};
    ans=0;
    for(val=1;val>=-1;val-=2)
    {
        for(i=1;i<=nr;i++)
        {
            update(vv[i].second,(vv[i].first-vv[i+1].first)*val);
            if(val==1)
                ans+=1LL*compute(vv[i].second-1)*(vv[i].first-vv[i+1].first);
        }
    }
}
void nttttttttt(int x,int col)
{
    int wh;
    while(x!=0)
    {
        wh=p[x];
        while(l[wh].size()&&lev[l[wh].back().first]<=lev[x])
            l[wh].pop_back();
        l[wh].push_back({x,col});
        x=tt[p[x]];
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>c[i],x[i]=c[i];
    sort(x+1,x+n+1);
    for(i=1;i<=n;i++)
        norm[x[i]]=i;
    for(i=1;i<=n;i++)
        c[i]=norm[c[i]];
    for(i=1;i<=n-1;i++)
    {
        cin>>a[i]>>b[i];
        v[a[i]].push_back(b[i]);
    }
    lev[1]=1;
    dfs(1);
    l[p[1]].push_back({1,c[1]});
    for(int cnt=1;cnt<=n-1;cnt++)
    {
        ffffffffft(a[cnt]);
        nttttttttt(b[cnt],c[b[cnt]]);
        cout<<ans<<'\n';
    }
    return 0;
}

Compilation message (stderr)

construction.cpp: In function 'void dfs(int)':
construction.cpp:20:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
construction.cpp:30:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
construction.cpp: In function 'int get(int, int)':
construction.cpp:40:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ret+(1<<p)<l[wh].size()&&lev[l[wh][ret+(1<<p)].first]>=lev[x])
            ~~~~~~~~~~^~~~~~~~~~~~~
construction.cpp: In function 'void ffffffffft(int)':
construction.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=in;i<l[wh].size();i++)
                  ~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84