oj.uz

Submission #873486

# Submission time Handle Problem Language Result Execution time Memory
873486 2023-11-15T07:12:15 Z sleepntsheep Paths (RMI21_paths) C++17
31 / 100
 600 ms 18120 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()

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 4 ms 8796 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8796 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 136 ms 9536 KB Output is correct
4 Correct 413 ms 11236 KB Output is correct
5 Correct 98 ms 9248 KB Output is correct
6 Correct 274 ms 10264 KB Output is correct
7 Correct 184 ms 10056 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8796 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 136 ms 9536 KB Output is correct
4 Correct 413 ms 11236 KB Output is correct
5 Correct 98 ms 9248 KB Output is correct
6 Correct 274 ms 10264 KB Output is correct
7 Correct 184 ms 10056 KB Output is correct
8 Execution timed out 1052 ms 14672 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8796 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 136 ms 9536 KB Output is correct
4 Correct 413 ms 11236 KB Output is correct
5 Correct 98 ms 9248 KB Output is correct
6 Correct 274 ms 10264 KB Output is correct
7 Correct 184 ms 10056 KB Output is correct
8 Execution timed out 1052 ms 14672 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16212 KB Output is correct
2 Correct 58 ms 18120 KB Output is correct
3 Correct 40 ms 15856 KB Output is correct
4 Correct 40 ms 16208 KB Output is correct
5 Correct 40 ms 17072 KB Output is correct
6 Correct 37 ms 16328 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8796 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 136 ms 9536 KB Output is correct
4 Correct 413 ms 11236 KB Output is correct
5 Correct 98 ms 9248 KB Output is correct
6 Correct 274 ms 10264 KB Output is correct
7 Correct 184 ms 10056 KB Output is correct
8 Execution timed out 1052 ms 14672 KB Time limit exceeded
9 Halted 0 ms 0 KB -