Submission #173133

#	Time	Username	Problem	Language	Result	Execution time	Memory
173133		Akashi	Construction of Highway (JOI18_construction)	C++14	100 / 100	391 ms	107016 KiB

construction

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n;
int a[N], H[N], TT[N], sz[N], Next[N], x[N], y[N];
bool viz[N];
vector <int> v[N];
deque <pair <int, int> > L[N];
vector <pair <int, int> > aux, tmp;
vector <int> val;

void adfs(int nod = 1){
    sz[nod] = 1;
    for(auto &it : v[nod]){
        TT[it] = nod; H[it] = H[nod] + 1;
        adfs(it);
        if(sz[it] > sz[v[nod][0]]) swap(it, v[nod][0]);
    }
}

void bdfs(int nod = 1){
    if(v[nod].empty()) return ;
    Next[v[nod][0]] = Next[nod];
    bdfs(v[nod][0]);
    for(int i = 1; i < v[nod].size() ; ++i){
        Next[v[nod][i]] = v[nod][i];
        bdfs(v[nod][i]);
    }
}

int AS;
long long bit[N];

inline void C(){
    for(int i = 1; i <= AS ; ++i)
        bit[i] = 0;
}

inline void U(int x, int val){
    for(int i = x; i <= AS ; i = i + (i & (-i)))
        bit[i] += val;
}

inline long long Q(int x){
    long long Sol = 0;
    for(int i = x; i > 0 ; i = i - (i & (-i)))
        Sol += bit[i];
    return Sol;
}

long long calc_path(int nod){
    aux.clear(); val.clear();

    while(nod != 0){
        int p = Next[nod];
        int S = H[nod] - H[p] + 1;

        int NR = 0;
        tmp.clear();
        for(auto it : L[p]){
            if(NR + it.second < S) NR = NR + it.second, tmp.push_back({it.first, it.second});
            else {tmp.push_back({it.first, S - NR}), NR = S; break ;}
        }

        for(vector <pair <int, int> > :: reverse_iterator it = tmp.rbegin() ; it != tmp.rend() ; ++it)
            aux.push_back({it->first, it->second});

        nod = TT[p];
    }

    for(auto it : aux) val.push_back(it.first);
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());

    AS = val.size();
    C();
    long long Sum = 0, Sol = 0;
    for(auto it : aux){
        int pos = lower_bound(val.begin(), val.end(), it.first) - val.begin() + 1;
        Sol = Sol + 1LL * it.second * Q(pos - 1);

        Sum += it.second;
        U(pos, it.second);
    }

    return Sol;
}

void update(int nod, int val){
    while(nod != 0){
        int p = Next[nod];
        int S = H[nod] - H[p] + 1;

        int NR = 0;
        while(NR < S && !L[p].empty()){
            if(NR + L[p].front().second <= S) NR = NR + L[p].front().second, L[p].pop_front();
            else{
                L[p].front().second -= (S - NR);
                NR = S;
            }
        }
        L[p].push_front({val, S});

        nod = TT[p];
    }
}

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

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

    adfs();
    Next[1] = 1;
    bdfs();

    for(int i = 1; i < n ; ++i){
        printf("%d\n", calc_path(x[i]));
        update(y[i], a[y[i]]);
    }

    return 0;
}

Compilation message (stderr)

construction.cpp: In function 'void bdfs(int)':
construction.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < v[nod].size() ; ++i){
                    ~~^~~~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:125:39: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
         printf("%d\n", calc_path(x[i]));
                        ~~~~~~~~~~~~~~~^
construction.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
construction.cpp:113:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n ; ++i) scanf("%d", &a[i]);
                                  ~~~~~^~~~~~~~~~~~~
construction.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x[i], &y[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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