oj.uz

Submission #873478

# Submission time Handle Problem Language Result Execution time Memory
873478 2023-11-15T07:04:12 Z sleepntsheep Paths (RMI21_paths) C++17
48 / 100
 336 ms 18004 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)
        {
            lz[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;
            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 6744 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 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 9 ms 6916 KB Output is correct
4 Correct 6 ms 6748 KB Output is correct
5 Correct 7 ms 6916 KB Output is correct
6 Correct 6 ms 6916 KB Output is correct
7 Correct 6 ms 6748 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 9 ms 6916 KB Output is correct
4 Correct 6 ms 6748 KB Output is correct
5 Correct 7 ms 6916 KB Output is correct
6 Correct 6 ms 6916 KB Output is correct
7 Correct 6 ms 6748 KB Output is correct
8 Correct 157 ms 6744 KB Output is correct
9 Correct 153 ms 6748 KB Output is correct
10 Correct 104 ms 7184 KB Output is correct
11 Correct 336 ms 6936 KB Output is correct
12 Correct 132 ms 6748 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 9 ms 6916 KB Output is correct
4 Correct 6 ms 6748 KB Output is correct
5 Correct 7 ms 6916 KB Output is correct
6 Correct 6 ms 6916 KB Output is correct
7 Correct 6 ms 6748 KB Output is correct
8 Correct 157 ms 6744 KB Output is correct
9 Correct 153 ms 6748 KB Output is correct
10 Correct 104 ms 7184 KB Output is correct
11 Correct 336 ms 6936 KB Output is correct
12 Correct 132 ms 6748 KB Output is correct
13 Incorrect 215 ms 9104 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 41 ms 16292 KB Output is correct
2 Correct 48 ms 18004 KB Output is correct
3 Correct 40 ms 15924 KB Output is correct
4 Correct 43 ms 16220 KB Output is correct
5 Correct 52 ms 17248 KB Output is correct
6 Correct 39 ms 16080 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 9 ms 6916 KB Output is correct
4 Correct 6 ms 6748 KB Output is correct
5 Correct 7 ms 6916 KB Output is correct
6 Correct 6 ms 6916 KB Output is correct
7 Correct 6 ms 6748 KB Output is correct
8 Correct 157 ms 6744 KB Output is correct
9 Correct 153 ms 6748 KB Output is correct
10 Correct 104 ms 7184 KB Output is correct
11 Correct 336 ms 6936 KB Output is correct
12 Correct 132 ms 6748 KB Output is correct
13 Incorrect 215 ms 9104 KB Output isn't correct
14 Halted 0 ms 0 KB -