oj.uz

Submission #873482

# Submission time Handle Problem Language Result Execution time Memory
873482 2023-11-15T07:09:03 Z sleepntsheep Paths (RMI21_paths) C++17
48 / 100
 339 ms 18000 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];
    ll rt[N]{0};

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

        void build(int v, int l, int r)
        {
            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;
            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]);
        }

        void reset()
        {
            memset(lz,0,sizeof lz);
        }
    } 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;
    int del[2010]{0};
    void process()
    {
        pair<ll,int> x = t.qry(0,n-1,0,0,n-1);
        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];
            if(!del[c]) t.upd(tin[c], tout[c], -w, 0, 0, n-1), del[c]=1;
        }
    }

    ll oneroot(int root)
    {
        memset(rt,0,sizeof rt);
        memset(rv,0,sizeof rv);
        memset(del,0,sizeof del);
        memset(P,0,sizeof P);
        rt[root]=ans=timer=0;
        dfs1(root,root);
        assert(timer==n);
        t.reset();
        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 <= 1002)
    {
        for (int i = 1; i <= n; ++i) cout << sub123::oneroot(i) << '\n';
    }
    else if (n <= 2000)
    {
        for (int i = 1; i <= n; ++i) cout << sub4::oneroot(i) << '\n';
    }
    else
    {
    }

    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 5 ms 6748 KB Output is correct
4 Correct 6 ms 6916 KB Output is correct
5 Correct 7 ms 6744 KB Output is correct
6 Correct 5 ms 6748 KB Output is correct
7 Correct 6 ms 6920 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 5 ms 6748 KB Output is correct
4 Correct 6 ms 6916 KB Output is correct
5 Correct 7 ms 6744 KB Output is correct
6 Correct 5 ms 6748 KB Output is correct
7 Correct 6 ms 6920 KB Output is correct
8 Correct 160 ms 6996 KB Output is correct
9 Correct 150 ms 6972 KB Output is correct
10 Correct 94 ms 6940 KB Output is correct
11 Correct 339 ms 6996 KB Output is correct
12 Correct 133 ms 6936 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 5 ms 6748 KB Output is correct
4 Correct 6 ms 6916 KB Output is correct
5 Correct 7 ms 6744 KB Output is correct
6 Correct 5 ms 6748 KB Output is correct
7 Correct 6 ms 6920 KB Output is correct
8 Correct 160 ms 6996 KB Output is correct
9 Correct 150 ms 6972 KB Output is correct
10 Correct 94 ms 6940 KB Output is correct
11 Correct 339 ms 6996 KB Output is correct
12 Correct 133 ms 6936 KB Output is correct
13 Incorrect 206 ms 9088 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16400 KB Output is correct
2 Correct 47 ms 18000 KB Output is correct
3 Correct 38 ms 15816 KB Output is correct
4 Correct 42 ms 16192 KB Output is correct
5 Correct 41 ms 16980 KB Output is correct
6 Correct 38 ms 16344 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 5 ms 6748 KB Output is correct
4 Correct 6 ms 6916 KB Output is correct
5 Correct 7 ms 6744 KB Output is correct
6 Correct 5 ms 6748 KB Output is correct
7 Correct 6 ms 6920 KB Output is correct
8 Correct 160 ms 6996 KB Output is correct
9 Correct 150 ms 6972 KB Output is correct
10 Correct 94 ms 6940 KB Output is correct
11 Correct 339 ms 6996 KB Output is correct
12 Correct 133 ms 6936 KB Output is correct
13 Incorrect 206 ms 9088 KB Output isn't correct
14 Halted 0 ms 0 KB -