oj.uz

Submission #547315

# Submission time Handle Problem Language Result Execution time Memory
547315 2022-04-10T10:46:47 Z CPSC Magic Tree (CEOI19_magictree) C++14
34 / 100
 2000 ms 795920 KB 
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
#define pii pair <int, int>
#define pb push_back
using namespace std;
const int N = 1e5+5;
int t,n,a[N],m,k,tim[N],val[N],va,ti;
int ans,mx,p,vert,mp[N],cnt,dp[N][1005];
vector <int> v[N],vv;
void dfs(int a, int p) {
    for (int i = 0; i < v[a].size(); i++) {
        int to = v[a][i];
        if (to == p) continue;
        dfs(to,a);
    }
    for (int i = 1; i <= mx; i++) {
        int sum = 0;
        int sum1 = 0;
        for (int j = 0; j < v[a].size(); j++) {
            int to = v[a][j]; if (to == p) continue;
            sum += dp[to][i];
            sum1 += dp[to][tim[a]];
        }
        if (tim[a] <= i)
        dp[a][i] = max(sum, sum1 + val[a]);
        else dp[a][i] = sum;
        ans = max(ans, dp[a][i]);
    }
}
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for (int i = 2; i <= n; i++){
        cin>>p;
        v[p].pb(i);
        v[i].pb(p);
    }
    dfs(1,0);
    for (int i = 1; i <= m; i++){
        cin>>vert>>ti>>va;
        vv.pb(ti);
        tim[vert] = ti;
        val[vert] = va;
    }
    sort(vv.begin(),vv.end());
    for (int i = 0; i < vv.size(); i++) {
        if (i == 0)cnt++; else if (vv[i] != vv[i - 1]) cnt++;
        mp[vv[i]] = cnt;
    }
    for (int i = 1; i <= n; i++) {
        tim[i] = mp[tim[i]];
        mx = max(mx,tim[i]);
    }
    dfs(1,0);
    cout<<ans<<"\n";
}

Compilation message

magictree.cpp: In function 'void dfs(long long int, long long int)':
magictree.cpp:14:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
magictree.cpp:22:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for (int j = 0; j < v[a].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
magictree.cpp: At global scope:
magictree.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main() {
      | ^~~~
magictree.cpp: In function 'int main()':
magictree.cpp:49:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i = 0; i < vv.size(); i++) {
      |                     ~~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 1 ms 2676 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2092 ms 793692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9812 KB Output is correct
2 Correct 9 ms 9940 KB Output is correct
3 Correct 7 ms 9900 KB Output is correct
4 Execution timed out 2037 ms 86812 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 412040 KB Output is correct
2 Correct 250 ms 412408 KB Output is correct
3 Correct 206 ms 415992 KB Output is correct
4 Correct 215 ms 412988 KB Output is correct
5 Correct 195 ms 420396 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 1 ms 2676 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 239 ms 426196 KB Output is correct
11 Correct 296 ms 418292 KB Output is correct
12 Correct 243 ms 428992 KB Output is correct
13 Correct 208 ms 426300 KB Output is correct
14 Correct 209 ms 433316 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 161784 KB Output is correct
2 Correct 621 ms 795592 KB Output is correct
3 Correct 764 ms 795888 KB Output is correct
4 Correct 742 ms 795920 KB Output is correct
5 Execution timed out 2081 ms 795852 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 1 ms 2676 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 8 ms 9812 KB Output is correct
11 Correct 9 ms 9940 KB Output is correct
12 Correct 7 ms 9900 KB Output is correct
13 Execution timed out 2037 ms 86812 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 1 ms 2676 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Execution timed out 2092 ms 793692 KB Time limit exceeded
11 Halted 0 ms 0 KB -