oj.uz

답안 #90131

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90131 2018-12-20T13:41:21 Z Bodo171 바이오칩 (IZhO12_biochips) C++14
100 / 100
 660 ms 17088 KB 
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=200005;
vector<int> v[nmax];
int dp[2][nmax];
int rep[nmax],l[nmax],r[nmax],val[nmax];
int n,m,i,j,nr,tt,x,use;
void dfs(int x)
{
    rep[++nr]=x;l[x]=nr;
    for(int i=0;i<v[x].size();i++)
        dfs(v[x][i]);
    r[x]=nr;
}
int main()
{
   // freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        cin>>tt>>val[i];
        v[tt].push_back(i);
    }
    dfs(v[0][0]);
    for(i=0;i<=m;i++)
    {
      use=1-use;
      for(j=0;j<=n;j++)
        dp[1-use][j]=-(1<<30);
        for(j=1;j<=n;j++)
      {
        x=rep[j];
        dp[use][j]=max(dp[use][j],dp[use][j-1]);
        dp[1-use][r[x]]=max(dp[use][l[x]-1]+val[x],dp[1-use][r[x]]);
      }
    }
    cout<<dp[use][n];
    return 0;
}

Compilation message

biochips.cpp: In function 'void dfs(int)':
biochips.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
biochips.cpp: In function 'int main()':
biochips.cpp:31:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
       for(j=0;j<=n;j++)
       ^~~
biochips.cpp:33:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         for(j=1;j<=n;j++)
         ^~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5236 KB Output is correct
3 Correct 6 ms 5284 KB Output is correct
4 Correct 13 ms 5612 KB Output is correct
5 Correct 15 ms 5704 KB Output is correct
6 Correct 16 ms 5976 KB Output is correct
7 Correct 458 ms 11596 KB Output is correct
8 Correct 481 ms 13080 KB Output is correct
9 Correct 457 ms 15052 KB Output is correct
10 Correct 660 ms 17088 KB Output is correct