제출 #1224374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224374		Mighilon	Paths (RMI21_paths)	C++20	0 / 100	1097 ms	23272 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "../Library/debug.h"
#else
#define dbg(x...)
#endif
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) for (int i = 0; i < (a); ++i)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i)
#define trav(a, x) for (auto& a : x)
#define f first 
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
 
const char nl = '\n';
const int INF = 1e9;
// const ll MOD = 998244353;
const int mxN = -1;

vector<vi> adj;
vector<vi> dp,dp2;
vi e,c;
int n,k;

void dfs(int v,int p){
  vector<vpi> d(k+1);
  trav(_i,adj[v]){
    int u=e[_i]^v;
    if(u==p)continue;
    dfs(u,v);
    FOR(i,1,k+1){
      dp[v][i]=max(dp[v][i],dp[u][i]+c[_i]);
      d[i].pb({dp[u][i]+c[_i],u});
    }
    d[0].pb({0,-1});
  }
  FOR(i,1,k+1){
    sort(all(d[i]),greater<pi>());
  }
  if(sz(d[0])==0)return;
  // dbg(v)
  // dbg(d)
  FOR(j,1,k+1){
    FOR(i,1,j+1){
      if(j-i>i)continue;
      if(d[i][0].s!=d[j-i][0].s)
        dp[v][j]=max(dp[v][j],d[i][0].f+d[j-i][0].f);
      else{
        if(sz(d[i])>1)
          dp[v][j]=max(dp[v][j],d[i][1].f+d[j-i][0].f);
        if(sz(d[j-i])>1)
          dp[v][j]=max(dp[v][j],d[i][0].f+d[j-i][1].f);
      }
    }
  }
}

void dfs2(int v, int p){
  vector<vpi> d(k+1);
  trav(_i,adj[v]){
    int u=e[_i]^v;
    if(u==p)continue;
    FOR(i,1,k+1)
      d[i].pb({dp[u][i]+c[_i],u});
    d[0].pb({0,-1});
  }
  F0R(i,k+1){
    d[i].pb({dp2[v][i],v});
  }
  F0R(i,k+1){
    sort(all(d[i]),greater<pi>());
  }
  trav(_i,adj[v]){
    int u=e[_i]^v;
    if(u==p)continue;
    dbg(u)
    dbg(d)
    FOR(j,1,k+1){
      FOR(i,1,j+1){
        if(j-i>i)continue;
        int x=0,y=0;
        if(u==d[i][x].s) x++;
        if(u==d[j-i][y].s) y++;
        if(sz(d[i])>x && sz(d[j-i])>y && d[i][x].s!=d[j-i][y].s)
          dp2[u][j]=max(dp2[u][j],d[i][x].f+d[j-i][y].f+c[_i]);
        else{
          if(sz(d[i])>x+1 && sz(d[j-i])>y){
            x++;
            if(d[i][x].s==u)x++;
            if(sz(d[i])>x && sz(d[j-i])>y)
              dp2[u][j]=max(dp2[u][j],d[i][x].f+d[j-i][y].f+c[_i]);
            if(d[i][x-1].s==u)x--;
            x--;
          }
          if(sz(d[j-i])>y+1 && sz(d[i])>x){
            y++;
            if(d[j-i][y].s==u)y++;
            if(sz(d[j-i])>y && sz(d[i])>x)
              dp2[u][j]=max(dp2[u][j],d[i][x].f+d[j-i][y].f+c[_i]);
            if(d[j-i][y-1].s==u)y--;
            y--;
          }
        }
      }
    }
  }
  trav(_i,adj[v]){
    int u=e[_i]^v;
    if(u==p)continue;
    dfs2(u,v);
  }
}

 
void solve(){
  cin>>n>>k;
  dp.resize(n,vi(k+1));
  dp2.resize(n,vi(k+1));
  e.resize(n-1);
  c.resize(n-1);
  adj.resize(n);
  F0R(i,n-1){
    int a,b,co;
    cin>>a>>b>>co;--a,--b;
    e[i]=a^b;
    c[i]=co;
    adj[a].pb(i);
    adj[b].pb(i);
  }
  dbg(1)
  F0R(i,n){
    dp=vector<vi>(n,vi(k+1,0));
    dfs(i,-1);
    cout<<dp[i][k]<<nl;
  }

}
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    int TC = 1;
    // cin >> TC;
    while(TC--){
        solve();
    }
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32