oj.uz

Submission #873477

# Submission time Handle Problem Language Result Execution time Memory
873477 2023-11-15T07:03:12 Z sleepntsheep Paths (RMI21_paths) C++17
48 / 100
 343 ms 17972 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];
                lz[v]=0;
                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]);
        }
    } t;

    void dfs1(int u, int p)
    {
        rv[tin[u] = timer++] = u;
        for (auto [w, v] : g[u]) if (v-p) P[v][0]=u,P[v][1]=w,rt[v]=rt[u]+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; c; c = P[c][0])
        {
            int p = P[c][0], 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);
        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;
}

Compilation message

Main.cpp: In function 'void sub4::process()':
Main.cpp:146:17: warning: unused variable 'p' [-Wunused-variable]
  146 |             int p = P[c][0], w = P[c][1];
      |                 ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 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 1 ms 6748 KB Output is correct
3 Correct 6 ms 6748 KB Output is correct
4 Correct 7 ms 7004 KB Output is correct
5 Correct 7 ms 6748 KB Output is correct
6 Correct 8 ms 6748 KB Output is correct
7 Correct 8 ms 6908 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 1 ms 6748 KB Output is correct
3 Correct 6 ms 6748 KB Output is correct
4 Correct 7 ms 7004 KB Output is correct
5 Correct 7 ms 6748 KB Output is correct
6 Correct 8 ms 6748 KB Output is correct
7 Correct 8 ms 6908 KB Output is correct
8 Correct 171 ms 6940 KB Output is correct
9 Correct 150 ms 6744 KB Output is correct
10 Correct 101 ms 6992 KB Output is correct
11 Correct 343 ms 6748 KB Output is correct
12 Correct 134 ms 6928 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 1 ms 6748 KB Output is correct
3 Correct 6 ms 6748 KB Output is correct
4 Correct 7 ms 7004 KB Output is correct
5 Correct 7 ms 6748 KB Output is correct
6 Correct 8 ms 6748 KB Output is correct
7 Correct 8 ms 6908 KB Output is correct
8 Correct 171 ms 6940 KB Output is correct
9 Correct 150 ms 6744 KB Output is correct
10 Correct 101 ms 6992 KB Output is correct
11 Correct 343 ms 6748 KB Output is correct
12 Correct 134 ms 6928 KB Output is correct
13 Incorrect 211 ms 9108 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 44 ms 16324 KB Output is correct
2 Correct 44 ms 17972 KB Output is correct
3 Correct 40 ms 15956 KB Output is correct
4 Correct 41 ms 16328 KB Output is correct
5 Correct 43 ms 17136 KB Output is correct
6 Correct 40 ms 16076 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 1 ms 6748 KB Output is correct
3 Correct 6 ms 6748 KB Output is correct
4 Correct 7 ms 7004 KB Output is correct
5 Correct 7 ms 6748 KB Output is correct
6 Correct 8 ms 6748 KB Output is correct
7 Correct 8 ms 6908 KB Output is correct
8 Correct 171 ms 6940 KB Output is correct
9 Correct 150 ms 6744 KB Output is correct
10 Correct 101 ms 6992 KB Output is correct
11 Correct 343 ms 6748 KB Output is correct
12 Correct 134 ms 6928 KB Output is correct
13 Incorrect 211 ms 9108 KB Output isn't correct
14 Halted 0 ms 0 KB -