Submission #164057

#	Time	Username	Problem	Language	Result	Execution time	Memory
164057		georgerapeanu	Construction of Highway (JOI18_construction)	C++11	16 / 100	202 ms	29020 KiB

construction

#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 1e5;

int n;
int ferikire[NMAX + 5];

pair<int,int> edges[NMAX + 5];

vector<int> graph[NMAX + 5];
int fst[NMAX + 5];
int snd[NMAX + 5];
int euler_len;
int lant_father[NMAX + 5];
int lvl[NMAX + 5];
int when[NMAX + 5];

void predfs(int nod,int tata){
    lvl[nod] = 1 + lvl[tata];
    fst[nod] = ++euler_len;
    for(auto it:graph[nod]){
        if(it == tata){
            continue;
        }
        predfs(it,nod);
    }
    snd[nod] = euler_len;
}

pair<int,int> aint[NMAX + 5];

void update(int nod,int st,int dr,const int &pos,const pair<int,int> &val){
    if(dr < pos || st > pos){
        return;
    }

    if(st == dr){
        aint[nod] = val;
        return ;
    }

    int mid = (st + dr) / 2;

    update(nod * 2,st,mid,pos,val);
    update(nod * 2 + 1,mid + 1,dr,pos,val);

    if(when[aint[2 * nod].second] > when[aint[2 * nod + 1].second]){
        aint[nod] = aint[2 * nod];
    }
    else{
        aint[nod] = aint[2 * nod + 1];
    }
}

pair<int,int> query(int nod,int st,int dr,int l,int r){
    if(l > dr || r < st){
        return {0,-1};
    }

    if(l <= st && dr <= r){
        return aint[nod];
    }

    int mid = (st + dr) / 2;

    pair<int,int> a = query(nod * 2,st,mid,l,r);
    pair<int,int> b = query(nod * 2 + 1,mid + 1,dr,l,r);

    if(when[a.second] > when[b.second]){
        return a;
    }
    else{
        return b;
    }

}

int aib[NMAX + 5];
map<int,int> to_norm;

void aib_update(int pos,int val){
    for(;pos <= NMAX;pos += (-pos) & pos){
        aib[pos] += val;
    }
}

int aib_query(int pos){
    int ans = 0;

    for(;pos;pos -= (-pos) & pos){
        ans += aib[pos];
    }

    return ans;
}

int main(){

    scanf("%d",&n);

    for(int i = 1;i <= n;i++){
        scanf("%d",&ferikire[i]);
        to_norm[ferikire[i]] = 1;
    }

    int last = 0;

    for(auto &it:to_norm){
        it.second = ++last;
    }

    when[1] = 1;
    for(int i = 1;i < n;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        graph[x].push_back(y);
        graph[y].push_back(x);
        edges[i] = {x,y};
        when[y] = i + 1;
    }

    predfs(1,0);

    update(1,1,n,fst[1],{ferikire[1],1});
    lant_father[1] = 0;

    for(int i = 1;i < n;i++){
        int nod = edges[i].first;
        long long ans = 0;
        vector<pair<int,int> > to_clear;
        while(nod != 0){
            pair<int,int> _lant = query(1,1,n,fst[nod],snd[nod]);
            ans += 1LL * (lvl[nod] - lvl[lant_father[_lant.second]]) * aib_query(to_norm[_lant.first] - 1);
            aib_update(to_norm[_lant.first],lvl[nod] - lvl[lant_father[_lant.second]]);
            to_clear.push_back({to_norm[_lant.first],lvl[lant_father[_lant.second]] - lvl[nod]});
            int lst_nod = nod;
            nod = lant_father[_lant.second];
            lant_father[_lant.second] = lst_nod;
        }
        update(1,1,n,fst[edges[i].second],{ferikire[edges[i].second],edges[i].second});
        lant_father[edges[i].second] = 0;
        for(auto it:to_clear){
            aib_update(it.first,it.second);
        }
        printf("%lld\n",ans);
    }



    return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
construction.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&ferikire[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~
construction.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~

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