oj.uz

Submission #873487

# Submission time Handle Problem Language Result Execution time Memory
873487 2023-11-15T07:12:38 Z sleepntsheep Paths (RMI21_paths) C++17
48 / 100
 174 ms 18008 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)

#define N 200005
#define ALL(x) x.begin(), x.end()

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")


int n, k;
vector<pair<int, int>> g[N];

namespace sub123
{
    ll dp[1001][101];
    int sz[N];

    void dfs1(int u, int p)
    {
        dp[u][0] = dp[u][1] = 0;
        sz[u] = 1;
        for (auto [w, v] : g[u]) if (v != p)
        {
            dfs1(v, u);
            for (int i = sz[u]; i >= 0; --i)
                for (int j = 1; i+j <= k && j <= sz[v]; ++j)
                    dp[u][i+j] = max(dp[u][i+j], dp[u][i] + dp[v][j] + w);
            sz[u] += sz[v];
        }
    }

    ll oneroot(int u)
    {
        memset(dp, 0xbf, sizeof dp);
        dfs1(u, u);
        return dp[u][k];
    }
};

namespace sub5
{
    ll dp2[N], dp3[N], dp4[N];
    void dfs2(int u, int p)
    {
        dp2[u] = 0;
        for (auto [w, v] : g[u]) if (v != p)
        {
            dfs2(v, u);
            if (dp2[v] + w >= dp2[u]) dp3[u] = dp2[u], dp2[u] = dp2[v] + w;
            else if (dp2[v] + w >= dp3[u]) dp3[u] = dp2[v] + w;
        }
    }

    void dfs3(int u, int p)
    {
        for (auto [w, v] : g[u]) if (v != p)
        {
            if (dp2[v] + w == dp2[u]) dp4[v] = max(dp4[u] + w, dp3[u] + w);
            else dp4[v] = max(dp4[u] + w, dp2[u] + w);
            dfs3(v, u);
        }
    }
};

namespace sub4
{
    int tin[2001], tout[2001], timer, P[2001][2], rv[2001],del[2001];
    ll rt[N]{0};

    struct segtree
    {
        pair<ll, int> t[4005]; ll lz[4005]{0};
        segtree() { }

        void build(int v, int l, int r)
        {
            lz[v]=0;del[rv[v]]=0;
            if (l >= r) {
                int u = rv[l];
                if (tin[u]==tout[u]) t[v] = {rt[u], u};
                else t[v] = {-0,u};
                return;
            }
            int m = (l+r)/2,vl=v+1,vr=v+(m-l+1)*2;
            build(vl,l,m),build(vr,m+1,r);
            t[v]=max(t[vl],t[vr]);
        }

        void push(int v, int l, int r)
        {
            if (!lz[v])return;
            t[v].first+=lz[v];
            if(l-r)
            {
                int m = (l+r)/2,vl=v+1,vr=v+(m-l+1)*2;
                lz[vl]+=lz[v];lz[vr]+=lz[v];
            }
            lz[v]=0;
        }

        pair<ll, int> qry(int x, int y, int v, int l, int r)
        {
            push(v,l,r);
            if (y<l||r<x) return {-1e18, -1e9};
            if (x<=l&&r<=y)return t[v];
            int m = (l+r)/2,vl=v+1,vr=v+(m-l+1)*2;
            return max(qry(x, y, vl,l,m),qry(x,y,vr,m+1,r));
        }

        void upd(int x, int y, int k, int v, int l, int r)
        {
            push(v,l,r);
            if (y<l||r<x) return;
            if (x<=l&&r<=y){lz[v]=k;push(v,l,r);return;}
            int m = (l+r)/2,vl=v+1,vr=v+(m-l+1)*2;
            upd(x, y,k,vl,l,m),upd(x,y,k,vr,m+1,r);
            t[v]=max(t[vl],t[vr]);
        }

    } t;

    void dfs1(int u, int p)
    {
        rv[tin[u] = timer++] = u;
        for (auto [w, v] : g[u]) if (v-p) rt[v]=rt[P[v][0]=u]+(P[v][1]=w),dfs1(v, u);
        tout[u] = timer - 1;
    }

    ll ans;
    void process()
    {
        pair<ll,int> x = t.qry(0,n-1,0,0,n-1);
        //cerr<<"("<<x.first<<", "<<x.second<<")"<<endl;
        if (x.first <= 0) return;
        ans += x.first;
        for (int c = x.second; P[c][0]; c = P[c][0])
        {
            int w = P[c][1];
            //cerr<<"Erasing "<<-w<<endl;
            if(!del[c]) t.upd(tin[c], tout[c], -w, 0, 0, n-1), del[c]=1;
        }
    }

    ll oneroot(int root)
    {
        P[root][0]=P[root][1]=rt[root]=ans=timer=0;
        dfs1(root,root);
        t.build(0,0,n-1);
        for (int i = 1; i <= k; ++i) process();
        return ans;
    }
};

int main()
{
    ShinLena;
    cin >> n >> k;
    for (int u, v, w, i = 1; i < n; ++i) cin >> u >> v >> w, g[u].emplace_back(w, v), g[v].emplace_back(w, u);

    if (k == 1)
    {
        sub5::dfs2(1, 1);
        sub5::dfs3(1, 1);
        for (int i = 1; i <= n; ++i) cout << max(sub5::dp2[i], sub5::dp4[i]) << '\n';
    }
    else if (n <= 2000)
    {
        for (int i = 1; i <= n; ++i) cout << sub4::oneroot(i) << '\n';
    }
    else if (n <= 1002)
    {
        for (int i = 1; i <= n; ++i) cout << sub123::oneroot(i) << '\n';
    }
    else
    {
    }

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8896 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8896 KB Output is correct
3 Correct 5 ms 8796 KB Output is correct
4 Correct 7 ms 8980 KB Output is correct
5 Correct 4 ms 8792 KB Output is correct
6 Correct 7 ms 8984 KB Output is correct
7 Correct 6 ms 8796 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8896 KB Output is correct
3 Correct 5 ms 8796 KB Output is correct
4 Correct 7 ms 8980 KB Output is correct
5 Correct 4 ms 8792 KB Output is correct
6 Correct 7 ms 8984 KB Output is correct
7 Correct 6 ms 8796 KB Output is correct
8 Correct 116 ms 8796 KB Output is correct
9 Correct 174 ms 8792 KB Output is correct
10 Correct 169 ms 9008 KB Output is correct
11 Correct 60 ms 8976 KB Output is correct
12 Correct 107 ms 9032 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8896 KB Output is correct
3 Correct 5 ms 8796 KB Output is correct
4 Correct 7 ms 8980 KB Output is correct
5 Correct 4 ms 8792 KB Output is correct
6 Correct 7 ms 8984 KB Output is correct
7 Correct 6 ms 8796 KB Output is correct
8 Correct 116 ms 8796 KB Output is correct
9 Correct 174 ms 8792 KB Output is correct
10 Correct 169 ms 9008 KB Output is correct
11 Correct 60 ms 8976 KB Output is correct
12 Correct 107 ms 9032 KB Output is correct
13 Runtime error 9 ms 18008 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16284 KB Output is correct
2 Correct 41 ms 18000 KB Output is correct
3 Correct 43 ms 16000 KB Output is correct
4 Correct 40 ms 16284 KB Output is correct
5 Correct 42 ms 17088 KB Output is correct
6 Correct 38 ms 16080 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8896 KB Output is correct
3 Correct 5 ms 8796 KB Output is correct
4 Correct 7 ms 8980 KB Output is correct
5 Correct 4 ms 8792 KB Output is correct
6 Correct 7 ms 8984 KB Output is correct
7 Correct 6 ms 8796 KB Output is correct
8 Correct 116 ms 8796 KB Output is correct
9 Correct 174 ms 8792 KB Output is correct
10 Correct 169 ms 9008 KB Output is correct
11 Correct 60 ms 8976 KB Output is correct
12 Correct 107 ms 9032 KB Output is correct
13 Runtime error 9 ms 18008 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -