Submission #257783

#	Time	Username	Problem	Language	Result	Execution time	Memory
257783		uacoder123	Dostavljač (COCI18_dostavljac)	C++14	14 / 140	312 ms	2296 KiB

dostavljac

#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]=(node==1)?0:-1;
  for(int t=1;t<=m;++t)
  {
    dp[node][t]=(node==1)?val[node]:-1;
    for(int i=0;i<v.size();++i)
    {
      if(dis[v[i]][node]>t-1||dp[v[i]][t-1-dis[v[i]][node]]==-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];
  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 (stderr)

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: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14