oj.uz

Submission #305957

# Submission time Handle Problem Language Result Execution time Memory
305957 2020-09-24T07:31:11 Z aZvezda Biochips (IZhO12_biochips) C++14
100 / 100
 1107 ms 410092 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl

const int MAX_N = 2e5 + 10;
const int MAX_W = 510;
vector<int> g[MAX_N];
int in[MAX_N], out[MAX_N], arr[MAX_N];
int tme = -1;
int dp[MAX_N][MAX_W];

void dfs(int x) {
    in[x] = tme; tme ++;
    for(auto it : g[x]) {
        dfs(it);
    }
    out[x] = tme;
}

bool cmp(int a, int b) {
    return in[a] < in[b];
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, w;
    cin >> n >> w;
    vector<int> ord;
    for(int i = 1; i <= n; i ++) {
        int p;
        cin >> p >> arr[i];
        g[p].push_back(i);
        ord.push_back(i);
    }
    dfs(0);
    sort(ord.begin(), ord.end(), cmp);
    for(int i = 0; i < MAX_N; i ++) {fill_n(dp[i], MAX_W, -mod);}
    dp[0][0] = 0;
    int ret = 0;
    for(int i = 0; i < ord.size(); i ++) {
        chkmax(ret, dp[i][w]);
        for(int j = 0; j < MAX_W - 1; j ++) {
            chkmax(dp[i + 1][j], dp[i][j]);
            chkmax(dp[out[ord[i]]][j + 1], dp[i][j] + arr[ord[i]]);
        }
    }
    cout << max(ret, dp[ord.size()][w]) << endl;
    return 0;
}

Compilation message

biochips.cpp: In function 'int main()':
biochips.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i = 0; i < ord.size(); i ++) {
      |                    ~~^~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 404312 KB Output is correct
2 Correct 256 ms 404332 KB Output is correct
3 Correct 259 ms 404356 KB Output is correct
4 Correct 285 ms 404600 KB Output is correct
5 Correct 293 ms 404728 KB Output is correct
6 Correct 291 ms 404728 KB Output is correct
7 Correct 912 ms 409188 KB Output is correct
8 Correct 913 ms 409324 KB Output is correct
9 Correct 1022 ms 409580 KB Output is correct
10 Correct 1107 ms 410092 KB Output is correct