Submission #1075662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075662		Neco_arc	Construction of Highway (JOI18_construction)	C++17	100 / 100	235 ms	22224 KiB

construction

#include <bits/stdc++.h>
#ifdef LOCAL
#include <bits/debug.hpp>
#endif // LOCAL

#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "Construction of Highway"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 1e5 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

int n;
int a[maxn], h[maxn], par[maxn];
int nex[maxn], In[maxn], siz[maxn];
vector<int> edges[maxn];
vector<pair<int, int>> P[maxn];
pair<int, int> E[maxn];

/// DATA STRUCTURE
struct BIT {
    int bit[maxn];

    void update(int x, int val) {
        for(; x < maxn; x += (x & -x)) bit[x] += val;
    }

    int get(int x, int ans = 0) {
        for(; x > 0; x -= (x & -x)) ans += bit[x];
        return ans;
    }

} Bit;

/// PRE DFS
int dfs_siz(int u) {
    siz[u] = 1;
    for(int &v : edges[u]) {
        edges[v].erase(find(all(edges[v]), u));

        h[v] = h[u] + 1, par[v] = u;
        siz[u] += dfs_siz(v);
        if(siz[v] > siz[edges[u][0]]) swap(v, edges[u][0]);
    }
    return siz[u];
}

void dfs_hld(int u) {
    static int Time = 0;
    In[u] = ++Time;

    for(int v : edges[u]) {
        if(v == edges[u][0]) nex[v] = nex[u];
        else nex[v] = v;
        dfs_hld(v);
    }
}

/// HLD DECOMP <3
ll get(int u, int val) {

    ll ans = 0;
    vector<pair<int, int>> S, tmp;

    auto prog = [&](int u, int p) {
        int prv = h[p] - 1;
        tmp.clear();

        while(!P[p].empty() && h[P[p].back().first] < h[u]) {
            tmp.push_back({P[p].back().second, h[P[p].back().first] - prv});
            prv = h[P[p].back().first];
            P[p].pop_back();
        }

        if(!P[p].empty()) tmp.push_back({P[p].back().second, h[u] - prv});
        P[p].push_back({u, val});

        reverse(all(tmp));
        for(auto x : tmp) S.push_back(x);
    };

    for(; u != 0; u = par[nex[u]]) {
        prog(u, nex[u]);
    }


    for(auto [cl, w] : S) ans += 1ll * w * Bit.get(cl - 1), Bit.update(cl, w);
    for(auto [cl, w] : S) Bit.update(cl, -w);
    return ans;
}

void solve()
{
    vector<int> Comp;

    cin >> n;
    fi(i, 1, n) cin >> a[i], Comp.push_back(a[i]);
    fi(i, 1, n - 1) {
        int x, y; cin >> x >> y;

        E[i] = {x, y};
        edges[x].push_back(y), edges[y].push_back(x);
    }

    resp(Comp);
    fi(i, 1, n) a[i] = upper_bound(all(Comp), a[i]) - Comp.begin();

    nex[1] = h[1] = 1;
    dfs_siz(1), dfs_hld(1);
    get(1, a[1]);


    fi(i, 1, n - 1) {
        int x, y; tie(x, y) = E[i];
        cout << get(y, a[y]) << '\n';
    }

}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }


    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:139:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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