oj.uz

답안 #200954

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
200954 2020-02-08T19:37:47 Z Saboon Dostavljač (COCI18_dostavljac) C++14
126 / 140
 2000 ms 8152 KB 
#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

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.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 632 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 1144 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 760 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 2032 KB Output is correct
2 Correct 21 ms 1148 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1144 KB Output is correct
2 Correct 292 ms 3832 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 558 ms 5112 KB Output is correct
2 Correct 179 ms 2728 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 2936 KB Output is correct
2 Correct 1374 ms 6744 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1211 ms 6392 KB Output is correct
2 Correct 465 ms 3960 KB Output is correct

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2080 ms 8152 KB Time limit exceeded
2 Halted 0 ms 0 KB -