oj.uz

Submission #873476

# Submission time Handle Problem Language Result Execution time Memory
873476 2023-11-15T07:02:41 Z sleepntsheep Paths (RMI21_paths) C++17
48 / 100
 600 ms 17856 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] = {-1e17,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 (t[v].first>-1e17)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) 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);
        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 2 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 2 ms 6748 KB Output is correct
3 Correct 6 ms 6744 KB Output is correct
4 Correct 8 ms 6748 KB Output is correct
5 Correct 8 ms 6748 KB Output is correct
6 Correct 6 ms 6748 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 2 ms 6748 KB Output is correct
3 Correct 6 ms 6744 KB Output is correct
4 Correct 8 ms 6748 KB Output is correct
5 Correct 8 ms 6748 KB Output is correct
6 Correct 6 ms 6748 KB Output is correct
7 Correct 6 ms 6748 KB Output is correct
8 Correct 156 ms 6924 KB Output is correct
9 Correct 151 ms 6984 KB Output is correct
10 Correct 96 ms 6748 KB Output is correct
11 Correct 337 ms 6944 KB Output is correct
12 Correct 133 ms 6940 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 2 ms 6748 KB Output is correct
3 Correct 6 ms 6744 KB Output is correct
4 Correct 8 ms 6748 KB Output is correct
5 Correct 8 ms 6748 KB Output is correct
6 Correct 6 ms 6748 KB Output is correct
7 Correct 6 ms 6748 KB Output is correct
8 Correct 156 ms 6924 KB Output is correct
9 Correct 151 ms 6984 KB Output is correct
10 Correct 96 ms 6748 KB Output is correct
11 Correct 337 ms 6944 KB Output is correct
12 Correct 133 ms 6940 KB Output is correct
13 Execution timed out 920 ms 9052 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16408 KB Output is correct
2 Correct 50 ms 17856 KB Output is correct
3 Correct 38 ms 15976 KB Output is correct
4 Correct 44 ms 16216 KB Output is correct
5 Correct 43 ms 17072 KB Output is correct
6 Correct 38 ms 16076 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 2 ms 6748 KB Output is correct
3 Correct 6 ms 6744 KB Output is correct
4 Correct 8 ms 6748 KB Output is correct
5 Correct 8 ms 6748 KB Output is correct
6 Correct 6 ms 6748 KB Output is correct
7 Correct 6 ms 6748 KB Output is correct
8 Correct 156 ms 6924 KB Output is correct
9 Correct 151 ms 6984 KB Output is correct
10 Correct 96 ms 6748 KB Output is correct
11 Correct 337 ms 6944 KB Output is correct
12 Correct 133 ms 6940 KB Output is correct
13 Execution timed out 920 ms 9052 KB Time limit exceeded
14 Halted 0 ms 0 KB -