Submission #1285269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285269		Bui_Quoc_Cuong	Construction of Highway (JOI18_construction)	C++20	100 / 100	330 ms	19048 KiB

construction

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
const int maxn = 2e5 + 5;

int n;
int a[maxn];
vector <int> g[maxn];
int v[maxn];

int sz[maxn], heavy[maxn];
int head[maxn], cur[maxn], pos[maxn], timecrt, timedfs, par[maxn];

void dfs(int u)
{
    sz[u] = 1;
    for (int &v : g[u])
    {
        par[v] = u;
        dfs(v);
        sz[u]+= sz[v];
        if(sz[v] > sz[heavy[u]]) heavy[u] = v;
    }
}

void hld(int u)
{
    if (!head[timecrt]) head[timecrt] = u;
    pos[u] = ++ timedfs;
    cur[u] = timecrt;

    if (heavy[u])
        hld(heavy[u]);

    for (int &v : g[u]) if (v != heavy[u])
    {
        timecrt++;
        hld(v);
    }
}

int bit[maxn];

void upd (int u, int val)
{
    for (int i = u; i <= n; i+= i&-i) bit[i]+= val;
}

int get (int u)
{
    int res = 0;
    for (int i = u; i; i-= i&-i) res+= bit[i];
    return res;
}

int st[4 * maxn];

void pushdown (int id)
{
    if (st[id] == - 1) return;
    st[id << 1] = st[id << 1 | 1] = st[id];
}

void pushup (int id)
{
    if (st[id << 1] != st[id << 1 | 1]) st[id] = - 1;
    else st[id] = st[id << 1];
}

void update (int id, int l, int r, int u, int v, int val)
{
    if (l > v || r < u) return;
    if (l >= u && r <= v)
    {
        st[id] = val;
        return;
    }
    int mid = l + r >> 1;
    pushdown(id);

    update (id * 2, l, mid, u, v, val);
    update (id * 2 + 1, mid + 1, r, u, v, val);

    pushup(id);
}

stack <pair <int, int>> mem;

long long get (int id, int l, int r, int u, int v)
{
    if (l > v || r < u) return 0;
    if (l >= u && r <= v && st[id] != - 1)
    {
 //       cout << l << " " << r << " " << st[id] << '\n';
        long long res = 1LL * (r - l + 1) * get(st[id] - 1);
        upd(st[id], r - l + 1);
        mem.push({st[id], r - l + 1});
        return res;
    }
    if (l == r) return 0;
    int mid = l + r >> 1;
    pushdown(id);
    return  get(id * 2 + 1, mid + 1, r, u, v) + get(id * 2, l, mid, u, v);
}

long long add (int u) {
    update (1, 1, n, pos[u], pos[u], a[u]);
    int val = a[u];
    u = par[u];
    long long res = 0;

    while (u > 0)
    {
        res+= get(1, 1, n, pos[head[cur[u]]], pos[u]);
        update (1, 1, n, pos[head[cur[u]]], pos[u], val);
        u = par[head[cur[u]]];
    }

    while (!mem.empty())
    {
        upd (mem.top().first, - mem.top().second);
        mem.pop();
    }

    return res;
}

int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

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

    cin >> n;
    vector <int> values;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        values.pb(a[i]);
    }
    sort(values.begin(), values.end());
    values.resize(unique(values.begin(), values.end()) - values.begin());
    for (int i = 1; i <= n; i++) a[i] = upper_bound(values.begin(), values.end(), a[i]) - values.begin();

    for (int i = 1; i < n; i++)
    {
        int u; cin >> u >> v[i];
        g[u].push_back(v[i]);
    }

    memset(st, - 1, sizeof st);

    dfs(1);
    hld(1);
    add(1);

    for (int i = 1; i < n; i++)
        cout << add(v[i]) << '\n';

    return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         freopen(kieuoanh".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
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(kieuoanh".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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