Submission #85261

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
85261	2018-11-19T02:10:16 Z	zoooma13	Biochips (IZhO12_biochips)	C++14	100 / 100	387 ms	11828 KB

biochips

#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]);
                   ~~~~~^~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	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