oj.uz

Submission #671191

# Submission time Handle Problem Language Result Execution time Memory
671191 2022-12-12T10:28:13 Z Ronin13 Friend (IOI14_friend) C++14
100 / 100
 23 ms 3408 KB 
#include "friend.h"
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
// Find out best sample
const int nmax = 1e5 + 1;
int dp[nmax][2];
int findSample(int n,int confidence[],int host[],int protocol[]){
    int ans = 0;
    for(int i = 0; i < n; i++){
        dp[i][0] = confidence[i];
        dp[i][1] = 0;
    }
    for(int i= n - 1; i > 0; i--){
        int p = host[i];
        if(protocol[i] == 0){
            dp[p][1] = max(dp[i][0], dp[i][1]) + dp[p][1];
            dp[p][0] = dp[p][0] + dp[i][1];
        }
        if(protocol[i] == 1){
            dp[p][0] = max({dp[p][0] + dp[i][1], dp[p][1] + dp[i][0], dp[i][0] + dp[p][0]});
            dp[p][1] = dp[p][1] + dp[i][1];
        }
        if(protocol[i] == 2){
            dp[p][0] = max({dp[p][0] + dp[i][1], dp[p][1] + dp[i][0]});
            dp[p][1] = dp[p][1] + dp[i][1];
        }
    }
	return max(dp[0][0], dp[0][1]);
}

Compilation message

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:16:9: warning: unused variable 'ans' [-Wunused-variable]
   16 |     int ans = 0;
      |         ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 308 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 308 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 316 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 1 ms 228 KB Output is correct
20 Correct 1 ms 308 KB Output is correct
21 Correct 1 ms 340 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 316 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 23 ms 3408 KB Output is correct
13 Correct 12 ms 1876 KB Output is correct
14 Correct 21 ms 3112 KB Output is correct
15 Correct 23 ms 3028 KB Output is correct