oj.uz

Submission #873489

# Submission time Handle Problem Language Result Execution time Memory
873489 2023-11-15T07:14:56 Z sleepntsheep Paths (RMI21_paths) C++17
48 / 100
 600 ms 19548 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()

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")


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[2004], tout[2004], timer, P[2004][2], rv[4004],del[4004];
    ll rt[N]{0};

    struct segtree
    {
        pair<ll, int> t[8005]; ll lz[8005]{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 = 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 2 ms 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 5 ms 9064 KB Output is correct
4 Correct 7 ms 9148 KB Output is correct
5 Correct 5 ms 9148 KB Output is correct
6 Correct 7 ms 9052 KB Output is correct
7 Correct 8 ms 9104 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 5 ms 9064 KB Output is correct
4 Correct 7 ms 9148 KB Output is correct
5 Correct 5 ms 9148 KB Output is correct
6 Correct 7 ms 9052 KB Output is correct
7 Correct 8 ms 9104 KB Output is correct
8 Correct 116 ms 9052 KB Output is correct
9 Correct 176 ms 9052 KB Output is correct
10 Correct 173 ms 9052 KB Output is correct
11 Correct 65 ms 9048 KB Output is correct
12 Correct 106 ms 9168 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 5 ms 9064 KB Output is correct
4 Correct 7 ms 9148 KB Output is correct
5 Correct 5 ms 9148 KB Output is correct
6 Correct 7 ms 9052 KB Output is correct
7 Correct 8 ms 9104 KB Output is correct
8 Correct 116 ms 9052 KB Output is correct
9 Correct 176 ms 9052 KB Output is correct
10 Correct 173 ms 9052 KB Output is correct
11 Correct 65 ms 9048 KB Output is correct
12 Correct 106 ms 9168 KB Output is correct
13 Execution timed out 773 ms 9468 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 18004 KB Output is correct
2 Correct 57 ms 19548 KB Output is correct
3 Correct 37 ms 17488 KB Output is correct
4 Correct 39 ms 18000 KB Output is correct
5 Correct 43 ms 18672 KB Output is correct
6 Correct 37 ms 17984 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 5 ms 9064 KB Output is correct
4 Correct 7 ms 9148 KB Output is correct
5 Correct 5 ms 9148 KB Output is correct
6 Correct 7 ms 9052 KB Output is correct
7 Correct 8 ms 9104 KB Output is correct
8 Correct 116 ms 9052 KB Output is correct
9 Correct 176 ms 9052 KB Output is correct
10 Correct 173 ms 9052 KB Output is correct
11 Correct 65 ms 9048 KB Output is correct
12 Correct 106 ms 9168 KB Output is correct
13 Execution timed out 773 ms 9468 KB Time limit exceeded
14 Halted 0 ms 0 KB -