Submission #894956

#	Time	Username	Problem	Language	Result	Execution time	Memory
894956		Pragmatism	Paths (RMI21_paths)	C++17	100 / 100	220 ms	23376 KiB

Main

//Bismillahir-Rahmanir-Rahim

#include <bits/stdc++.h>
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,popcnt,avx,avx2")

#define pb push_back
#define pii pair <int, int>
#define pll pair <long long, long long>
#define pld pair <long double, long double>
#define ll long long
#define ld long double
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define skip continue
#define bpop(x) (ll)__builtin_popcountll(x)

using namespace std;

const int N = 1e5 + 7;
const int M = 62;
const int maxA = 1e7 + 7;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const ll MOD = 998244353;
const ld eps = 1e-9;

pii dir[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define int long long

pii mx[N];
vector <pii> g[N];
int n, k, T, ans[N], dist[N];
set <pii> best, extra;
int sum_best = 0, sum_extra = 0;
void add(pii val) {
    //cout << "add: " << val.x << ' ' << val.y << '\n';
    best.insert(val), sum_best += val.x;
    if (sz(best) > k) {
        pii x = *best.begin();
        best.erase(x), extra.insert(x);
        sum_best -= x.x, sum_extra += x.x;
    }
}
void del(pii val) {
    //cout << "del: " << val.x << ' ' << val.y << '\n';
    if (best.count(val)) {
        best.erase(val), sum_best -= val.x;
        pii x = *extra.rbegin();
        extra.erase(x), sum_extra -= x.x;
        //cout << "del + ";
        add(x);
    }
    else {
        extra.erase(val);
        sum_extra -= val.x;
    }
}
void build(int v, int pr) {
    mx[v] = {dist[v], v};
    for (auto p : g[v]) {
        int to = p.x, w = p.y;
        if (to == pr)skip;
        dist[to] = dist[v] + w, build(to, v);
        mx[v] = max(mx[v], mx[to]);
    }
}
void build2(int v, int pr) {
    if (pr == 0 || mx[v].y != mx[pr].y)add({mx[v].x - dist[pr], mx[v].y});
    for (auto p : g[v]) {
        int to = p.x, w = p.y;
        if (to == pr)skip;
        build2(to, v);
    }
}
pii mxup[N];
void dfs(int v, int pr, int sub) {
    ans[v] = sum_best;
    pii mx1 = {0, 0}, mx2 = {0, 0};
    for (auto p : g[v]) {
        int to = p.x, w = p.y;
        if (to == pr)skip;
        if (mx[to].x - sub > mx1.x)mx2 = mx1, mx1 = {mx[to].x - sub, mx[to].y};
        else mx2 = max(mx2, {mx[to].x - sub, mx[to].y});
    }
    //cout << v << ":\n";
    //for (auto p : extra)cout << p.x << ' ' << p.y << '\n';
    //cout << '\n';
    //for (auto p : best)cout << p.x << ' ' << p.y << '\n';
    //cout << '\n';
    for (auto p : g[v]) {
        int to = p.x, w = p.y;
        if (to == pr)skip;
        //cout << v << "<->" << to << ":\n";
        pii val = max(((pii){mx[to].x - sub, mx[to].y} == mx1 ? mx2 : mx1), mxup[v]);
        del(val), add({val.x + w, val.y}), del({mx[to].x - sub, mx[to].y}), add({mx[to].x - w - sub, mx[to].y});
        mxup[to] = pii{val.x + w, val.y};
        dfs(to, v, sub + w);
        del({mx[to].x - w - sub, mx[to].y}), add({mx[to].x - sub, mx[to].y}), del({val.x + w, val.y}), add(val);
    }
}
void solve() {
    cin >> n >> k;
    int total = 0, cnt_leaf = 0;
    for (int i = 1;i < n;i++) {
        int x, y, w;
        cin >> x >> y >> w;
        g[x].pb({y, w}), g[y].pb({x, w});
        total += w;
    }
    for (int i = 1;i <= n;i++)cnt_leaf += (sz(g[i]) == 1);
    build(1, 0), build2(1, 0);
    if (sz(g[1]) == 1)add({0, 1});
    //k = min(k, sz(best) + sz(extra));
    //cout << "GAY:\n";
    //for (auto p : extra)cout << p.x << ' ' << p.y << '\n';
    //for (auto p : best)cout << p.x << ' ' << p.y << '\n';
    //cout << ":GAY\n";
    dfs(1, 0, 0);
    for (int i = 1;i <= n;i++)cout << ans[i] << '\n';
}
signed main() {
    //srand(time(NULL));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("tests.in", "r", stdin);
    //freopen("milkorder.out", "w", stdout);
    int test = 1;
    //cin >> test;
    for (int t = 1;t <= test;t++) {
        //cout << "Case " << t << ": ";
        solve();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void build2(long long int, long long int)':
Main.cpp:77:23: warning: unused variable 'w' [-Wunused-variable]
   77 |         int to = p.x, w = p.y;
      |                       ^
Main.cpp: In function 'void dfs(long long int, long long int, long long int)':
Main.cpp:87:23: warning: unused variable 'w' [-Wunused-variable]
   87 |         int to = p.x, w = p.y;
      |                       ^

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 12 / 12
• Subtask 6: 32 / 32