oj.uz

Submission #537695

# Submission time Handle Problem Language Result Execution time Memory
537695 2022-03-15T11:39:14 Z zaneyu Paths (RMI21_paths) C++14
31 / 100
 600 ms 18568 KB 
/*input
11 1
1 2 5
2 3 3
2 6 5
3 4 4
3 5 2
1 7 6
7 8 4
7 9 5
1 10 1
10 11 1
*/
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define MNTO(x,y) x=min(x,y)
#define MXTO(x,y) x=max(x,y)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define ld long double
#define sz(x) (int)x.size()
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
const int maxn=1e5+5;
vector<pii> v[maxn];
ll dp[1005][1005];
int dep[maxn];
ll dist[maxn];
int k;
int par[maxn][20];
int dfs(int u,int p){
    
    int s=(sz(v[u])==1);
    for(auto x:v[u]){
        if(x.f==p) continue;
        s+=dfs(x.f,u);
        for(int j=min(s,k);j>=0;j--){
            REP1(z,min(s,k)-j){
                MXTO(dp[u][j+z],dp[u][j]+dp[x.f][z]+x.s);
                if(!dp[x.f][z]) break;
            }
        }
    }
    return s;
}
void dfs2(int u,int p){
    par[u][0]=p;
    for(auto x:v[u]){
        if(x.f==p) continue;
        dep[x.f]=dep[u]+1;
        dist[x.f]=dist[u]+x.s;
        dfs2(x.f,u);
    }
}
ll d2[maxn];
void dfs3(int u,int p){
    for(auto x:v[u]){
        if(x.f==p) continue;
        d2[x.f]=d2[u]+x.s;
        dfs3(x.f,u);
    } 
}
#define lowb(x) x&(-x)
int lca(int a,int b){
    if(dep[a]<dep[b]) swap(a,b);
    int d=dep[a]-dep[b];
    while(d){
        int z=__lg(lowb(d));
        a=par[a][z];
        d-=lowb(d);
    }
    if(a==b) return a;
    for(int j=19;j>=0;j--){
        if(par[a][j]!=par[b][j]){
            a=par[a][j],b=par[b][j];
        }
    }
    return par[a][0];
}
ll get(int a,int b){
    return dist[a]+dist[b]-2*dist[lca(a,b)];
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n;
    cin>>n>>k;
    REP(i,n-1){
        int a,b,c;
        cin>>a>>b>>c;
        --a,--b;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    if(k==1){
        dfs2(0,-1);
        REP1(j,19){
            REP(i,n){
                if(par[i][j-1]!=-1) par[i][j]=par[par[i][j-1]][j-1];
                else par[i][j]=-1;
            }
        }
        dfs3(0,-1);
        int p=max_element(d2,d2+n)-d2;
        int a=p;
        d2[p]=0;
        dfs3(p,-1);
        p=max_element(d2,d2+n)-d2;
        REP(i,n){
            cout<<max(get(i,p),get(i,a))<<'\n';
        }
        return 0;
    }
    dfs(0,-1);
    REP(i,n){
        REP(j,n) REP(a,k+1) dp[j][a]=0;
        dfs(i,-1);
        cout<<dp[i][k]<<'\n';
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 5 ms 3412 KB Output is correct
4 Correct 9 ms 3456 KB Output is correct
5 Correct 5 ms 3528 KB Output is correct
6 Correct 4 ms 3412 KB Output is correct
7 Correct 5 ms 3412 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 5 ms 3412 KB Output is correct
4 Correct 9 ms 3456 KB Output is correct
5 Correct 5 ms 3528 KB Output is correct
6 Correct 4 ms 3412 KB Output is correct
7 Correct 5 ms 3412 KB Output is correct
8 Correct 260 ms 7516 KB Output is correct
9 Execution timed out 889 ms 7124 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 5 ms 3412 KB Output is correct
4 Correct 9 ms 3456 KB Output is correct
5 Correct 5 ms 3528 KB Output is correct
6 Correct 4 ms 3412 KB Output is correct
7 Correct 5 ms 3412 KB Output is correct
8 Correct 260 ms 7516 KB Output is correct
9 Execution timed out 889 ms 7124 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 17336 KB Output is correct
2 Correct 125 ms 18568 KB Output is correct
3 Correct 97 ms 16928 KB Output is correct
4 Correct 95 ms 17176 KB Output is correct
5 Correct 147 ms 17968 KB Output is correct
6 Correct 128 ms 17220 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 5 ms 3412 KB Output is correct
4 Correct 9 ms 3456 KB Output is correct
5 Correct 5 ms 3528 KB Output is correct
6 Correct 4 ms 3412 KB Output is correct
7 Correct 5 ms 3412 KB Output is correct
8 Correct 260 ms 7516 KB Output is correct
9 Execution timed out 889 ms 7124 KB Time limit exceeded
10 Halted 0 ms 0 KB -