oj.uz

답안 #257768

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
257768 2020-08-04T18:28:16 Z uacoder123 Dostavljač (COCI18_dostavljac) C++14
0 / 140
 270 ms 2296 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))

typedef int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
typedef tree<pair<lli,int>,null_type,less<pair<lli,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int n,m;
vi al[501],v;
int dp[501][501],lev[500],ans=0,val[501],par[501][11],dis[501][501],din[501],dout[501],ti=0;
bool isa(int u,int v)
{
  return (din[u]<=din[v])&&(dout[u]>=dout[v]);
}
int lca(int u,int v)
{
  if(isa(u,v))
    return(u);
  if(isa(v,u))
    return(v);
  for(int i=10;i>=0;--i)
    if(!isa(par[u][i],v))
      u=par[u][i];
  return(par[u][0]);
}
void dfs(int node,int p,int l)
{
  par[node][0]=p;
  lev[node]=l;
  din[node]=ti++;
  for(int i=1;i<11;++i)
    par[node][i]=par[par[node][i-1]][i-1];
  for(int i=0;i<al[node].size();++i)
    if(al[node][i]!=p)
      dfs(al[node][i],node,l+1);
  dout[node]=ti++;
}
void dfs2(int node,int p)
{
  dp[node][0]=0;
  for(int t=1;t<=m;++t)
  {
    dp[node][t]=0;
    for(int i=0;i<v.size();++i)
    {
      if(dis[v[i]][node]>t-1)
        continue;
      dp[node][t]=max(dp[node][t],val[node]+dp[v[i]][t-1-dis[v[i]][node]]);
    }
    ans=max(ans,dp[node][t]);
  }
  v.pb(node);
  for(int i=0;i<al[node].size();++i)
    if(al[node][i]!=p)
      dfs2(al[node][i],node);
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin>>n>>m;
  for(int i=1;i<=n;++i)
    cin>>val[i];
  v.pb(0);
  lev[0]=0;
  for(int i=0;i<n-1;++i)
  {
    int f,s;
    cin>>f>>s;
    al[f].pb(s);
    al[s].pb(f);
  }
  dfs(1,1,0);
  for(int i=1;i<=n;++i)
  {
    for(int j=1;j<=n;++j)
    {
      int l=lca(i,j);
      dis[i][j]=(lev[i]-lev[l])+lev[j]-lev[l];
    }
    dis[0][i]=lev[i];
    dis[i][0]=lev[i];
  }
  dfs2(1,1);
  cout<<ans<<endl;
  return(0);
}

Compilation message

dostavljac.cpp: In function 'void dfs(int, int, int)':
dostavljac.cpp:45:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<al[node].size();++i)
               ~^~~~~~~~~~~~~~~~
dostavljac.cpp: In function 'void dfs2(int, int)':
dostavljac.cpp:56:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size();++i)
                 ~^~~~~~~~~
dostavljac.cpp:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<al[node].size();++i)
               ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 512 KB Output isn't correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 512 KB Output isn't correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 640 KB Output isn't correct

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 1024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 1536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 157 ms 1912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 270 ms 2296 KB Output isn't correct
2 Halted 0 ms 0 KB -