답안 #85261

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
85261 2018-11-19T02:10:16 Z zoooma13 바이오칩 (IZhO12_biochips) C++14
100 / 100
387 ms 11828 KB
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 200005
#define MAX_M 502
#define INF 0x3f3f3f3f

int N ,M;
int A ,B;
int Mem[MAX_N];
vector <int> Adj[MAX_N];

int dp[MAX_M];
vector <int> Solve(int v)
{
    vector <int> ans = {0 ,0};
    for(int i : Adj[v])
    {
        vector <int> ch = Solve(i);
        vector <int> best(min(M+1 ,(int)(ans.size()+ch.size())) ,0);

        for(int j=0; j<ch.size(); j++)
        for(int k=0; k<ans.size() && k<=M-j; k++)
            best[j+k] = max(best[j+k] ,ans[k] + ch[j]);

        ans = best;
    }

    ans[1] = max(ans[1] ,Mem[v]);
    return ans;
}

int main()
{
    scanf("%d%d",&N,&M); assert(N < MAX_N && M < MAX_M);

    int root;
    for(int i=1; i<=N; i++)
    {
        scanf("%d%d",&A,&B);

        Mem[i] = B;
        if(A == 0)
            root = i;
        else
            Adj[A].push_back(i);
    }

    printf("%d\n",Solve(root)[M]);
}

Compilation message

biochips.cpp: In function 'std::vector<int> Solve(int)':
biochips.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<ch.size(); j++)
                      ~^~~~~~~~~~
biochips.cpp:23:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int k=0; k<ans.size() && k<=M-j; k++)
                      ~^~~~~~~~~~~
biochips.cpp: In function 'int main()':
biochips.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&N,&M); assert(N < MAX_N && M < MAX_M);
     ~~~~~^~~~~~~~~~~~~~
biochips.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&A,&B);
         ~~~~~^~~~~~~~~~~~~~
biochips.cpp:49:24: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
     printf("%d\n",Solve(root)[M]);
                   ~~~~~^~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4988 KB Output is correct
3 Correct 6 ms 5028 KB Output is correct
4 Correct 12 ms 5292 KB Output is correct
5 Correct 14 ms 5492 KB Output is correct
6 Correct 13 ms 5492 KB Output is correct
7 Correct 224 ms 6888 KB Output is correct
8 Correct 252 ms 8552 KB Output is correct
9 Correct 301 ms 10080 KB Output is correct
10 Correct 387 ms 11828 KB Output is correct