Submission #991979

#	Time	Username	Problem	Language	Result	Execution time	Memory
991979		prvocislo	Construction of Highway (JOI18_construction)	C++17	0 / 100	1 ms	348 KiB

construction

#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

const int inf = 1e9 + 5;
struct intervalac
{
    int n;
    vector<int> st;
    void init(int N) { n = N, st.assign(2 * n, 0); }
    void upd(int i, int x) { for (i += n; i > 0; i >>= 1) st[i] += x; }
    ll query(int l, int r)
    {
        int ans = 0;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
        {
            if (l & 1) ans += st[l++];
            if (r & 1) ans += st[--r];
        }
        return ans;
    }
};
int n;
int cnt = 0;
vector<set<pair<pair<int, int>, int> > > zac; // zaciatky usekov v retaziach
vector<int> r, s, h, p, d, a, b, c; // moja retaz, moja velkost, najvyssi v mojej retazi, moj otec
vector<vector<int> > g;
void dfss(int u)
{
    s[u] = 1;
    for (int v : g[u]) d[v] = d[u] + 1, dfss(v), s[u] += s[v];
}
void dfs(int u)
{
    if (r[u] == -1) h[cnt] = u, r[u] = cnt++;

    int v2 = -1;
    for (int v : g[u]) if (v2 == -1 || s[v] > s[v2]) v2 = v;

    if (v2 != -1) r[v2] = r[u];
    else zac[r[u]].insert({ {d[h[r[u]]], d[u]}, c[n] });

    for (int v : g[u]) dfs(v);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    zac.assign(n, {}), r.assign(n, -1), s.assign(n, -1), h.assign(n, -1), p.assign(n, 0), d.assign(n, 0), a.assign(n - 1, 0), b.assign(n - 1, 0), c.assign(n, 0), g.assign(n, {});
    for (int i = 0; i < n; i++) cin >> c[i];
    c.push_back(n);
    vector<int> c2 = c;
    sort(c2.begin(), c2.end());
    for (int i = 0; i <= n; i++) c[i] = lower_bound(c2.begin(), c2.end(), c[i]) - c2.begin();
    for (int i = 0; i < n - 1; i++) cin >> a[i] >> b[i], g[--a[i]].push_back(--b[i]), p[b[i]] = a[i];
    dfss(0);
    dfs(0);
    intervalac in;
    in.init(n + 1);
    for (int i = 0; i < n - 1; i++)
    {
        ll ans = 0;
        int u = b[i];
        vector<int> reset;
        while (true)
        {
            auto it = zac[r[u]].lower_bound({ {d[u] + 1, -1}, -1 });
            if (it == zac[r[u]].begin()) // uz sme vyhodili vsetky
            {
                zac[r[u]].insert({ {d[h[r[u]]], d[u]}, c[b[i]] });
                if (h[r[u]])
                {
                    u = p[h[r[u]]];
                    continue;
                }
                else break;
                continue;
            }
            it--;
            int dl = it->first.first, dr = it->first.second, col = it->second;
            reset.push_back(col);
            zac[r[u]].erase(it);
            ans += min(dr - dl + 1, d[u] - dl + 1) * 1ll * in.query(0, col - 1);
            in.upd(col, min(dr - dl + 1, d[u] - dl + 1));
            if (d[u] < dr) zac[r[u]].insert({ {d[u] + 1, dr}, col });
        }
        for (int j : reset) in.upd(j, -in.st[n + 1 + j]);
        cout << ans << "\n";
    }
    return 0;
}

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