oj.uz

Submission #62905

# Submission time Handle Problem Language Result Execution time Memory
62905 2018-07-30T18:07:21 Z zadrga Friend (IOI14_friend) C++14
100 / 100
 41 ms 2444 KB 
/*
Idea:
- http://blog.brucemerry.org.za/2014/07/ioi-2014-day-2-analysis.html (Friend)
*/

#include "friend.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF ((int) 1e9)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 100111

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

int val[maxn];

int findSample(int n, int confidence[], int host[], int protocol[]){
	for(int i = 0; i < n; i++)
		val[i] = confidence[i];

	int ans = 0;		
	for(int i = n - 1; i > 0; i--){
		int a = host[i];
		int b = i;

		if(protocol[i] == 0){
			ans += val[b];
			val[a] -= val[b];
			val[a] = max(val[a], 0);
		}
			
		if(protocol[i] == 1)
			val[a] += val[b];

		if(protocol[i] == 2)
			val[a] = max(val[a], val[b]);
	}

	ans += val[0];
	return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 568 KB Output is correct
4 Correct 2 ms 568 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 2 ms 568 KB Output is correct
8 Correct 3 ms 692 KB Output is correct
9 Correct 2 ms 692 KB Output is correct
10 Correct 3 ms 692 KB Output is correct
11 Correct 2 ms 692 KB Output is correct
12 Correct 2 ms 692 KB Output is correct
13 Correct 3 ms 692 KB Output is correct
14 Correct 3 ms 692 KB Output is correct
15 Correct 3 ms 692 KB Output is correct
16 Correct 2 ms 736 KB Output is correct
17 Correct 2 ms 736 KB Output is correct

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 740 KB Output is correct
2 Correct 3 ms 740 KB Output is correct
3 Correct 3 ms 744 KB Output is correct
4 Correct 4 ms 748 KB Output is correct
5 Correct 3 ms 752 KB Output is correct
6 Correct 4 ms 764 KB Output is correct
7 Correct 3 ms 776 KB Output is correct
8 Correct 4 ms 780 KB Output is correct
9 Correct 2 ms 792 KB Output is correct
10 Correct 3 ms 796 KB Output is correct
11 Correct 2 ms 800 KB Output is correct
12 Correct 3 ms 808 KB Output is correct
13 Correct 3 ms 820 KB Output is correct
14 Correct 3 ms 832 KB Output is correct
15 Correct 3 ms 836 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 848 KB Output is correct
2 Correct 3 ms 848 KB Output is correct
3 Correct 2 ms 848 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 4 ms 856 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 3 ms 864 KB Output is correct
8 Correct 2 ms 868 KB Output is correct
9 Correct 3 ms 872 KB Output is correct
10 Correct 3 ms 880 KB Output is correct
11 Correct 3 ms 892 KB Output is correct
12 Correct 3 ms 892 KB Output is correct
13 Correct 3 ms 896 KB Output is correct
14 Correct 3 ms 896 KB Output is correct
15 Correct 3 ms 896 KB Output is correct
16 Correct 3 ms 896 KB Output is correct
17 Correct 3 ms 896 KB Output is correct
18 Correct 2 ms 896 KB Output is correct
19 Correct 2 ms 896 KB Output is correct
20 Correct 3 ms 896 KB Output is correct
21 Correct 3 ms 896 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 2 ms 896 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 3 ms 900 KB Output is correct
5 Correct 3 ms 904 KB Output is correct
6 Correct 3 ms 908 KB Output is correct
7 Correct 2 ms 908 KB Output is correct
8 Correct 3 ms 908 KB Output is correct
9 Correct 3 ms 908 KB Output is correct
10 Correct 3 ms 908 KB Output is correct
11 Correct 2 ms 908 KB Output is correct
12 Correct 41 ms 2444 KB Output is correct
13 Correct 23 ms 2444 KB Output is correct
14 Correct 37 ms 2444 KB Output is correct
15 Correct 38 ms 2444 KB Output is correct