Submission #200954

#	Time	Username	Problem	Language	Result	Execution time	Memory
200954		Saboon	Dostavljač (COCI18_dostavljac)	C++14	126 / 140	2080 ms	8152 KiB

dostavljac

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <cstdlib>
#include <cctype>
#include <ctime>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <utility>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <list>
#include <bitset>
#include <complex>
//using namespace __gnu_pbds;
using namespace std;
#define f first
#define s second
#define endl '\n'
#define PB pop_back
#define pb push_back
#define mp make_pair
//#define int long long
#define sz(s) (int)s.size()
#define seper(n) setprecision(n)
#define all(v) v.begin(),v.end()
#define mem(a,b) memset(a,b,sizeof a)
#define IOS ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
//template<typename T>using ordered_set = tree<T , null_type , less_equal<T> , rb_tree_tag , tree_order_statistics_node_update>;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef map<int , int> mii;
typedef pair<int , int> pii;
typedef map<string , int> msi;
const int MAXN = 5e2 + 10;
int n , m , u , v , cnt , a[MAXN] , dp[2 + 1][MAXN][MAXN << 2];
mii mpp;
vector<int> adj[MAXN];
void dfs(int u , int p)
{
    int num = cnt;
    if(u != p)
        cnt += sz(adj[u]);
    else
        cnt += sz(adj[u]) + 1;
    for(auto v : adj[u])
        if(v != p)
            dfs(v , u);
    ///base
    for(int i = 1 ; i <= m ; i ++)
        dp[0][i][num] = a[u] , dp[1][i][num] = a[u];
    ///update
    for(auto v : adj[u])
        if(v != p)
        {
            num ++;
            for(int i = 0 ; i <= m ; i ++)
            {
                dp[0][i][num] = dp[0][i][num - 1] , dp[1][i][num] = dp[1][i][num - 1];
                for(int j = 0 ; i - j - 1 >= 0 ; j ++)
                {
                    dp[0][i][num] = max(dp[0][i][num] , dp[0][j][mpp[v]] + dp[1][i - j - 1][num - 1]);
                    if(i - j - 2 >= 0)
                        for(int bo = 0 ; bo < 2 ; bo ++)
                        {
                            if(!bo)
                                dp[bo][i][num] = max(dp[bo][i][num] , dp[bo ^ 1][j][mpp[v]] + dp[bo][i - j - 2][num - 1]);
                            else
                                dp[bo][i][num] = max(dp[bo][i][num] , dp[bo][j][mpp[v]] + dp[bo][i - j - 2][num - 1]);
                        }
                }
            }
        }
    mpp[u] = num;
}
int main()
{
    IOS
    scanf("%d%d" , &n , &m);
    for(int i = 0 ; i < n ; i ++)
        scanf("%d" , &a[i]);
    for(int i = 0 ; i < n - 1 ; i ++)
        scanf("%d%d" , &u , &v) , u -- , v -- , adj[u].pb(v) , adj[v].pb(u);
    dfs(0 , 0);
    printf("%d\n" , dp[0][m][mpp[0]]);
    return 0;
}

Compilation message (stderr)

dostavljac.cpp: In function 'int main()':
dostavljac.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d" , &n , &m);
     ~~~~~^~~~~~~~~~~~~~~~~~
dostavljac.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d" , &a[i]);
         ~~~~~^~~~~~~~~~~~~~
dostavljac.cpp:94:62: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d" , &u , &v) , u -- , v -- , adj[u].pb(v) , adj[v].pb(u);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 0 / 14