oj.uz

Submission #644580

# Submission time Handle Problem Language Result Execution time Memory
644580 2022-09-25T03:03:57 Z ymm Friend (IOI14_friend) C++17
100 / 100
 39 ms 7252 KB 
#include "friend.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

enum {
	FWP = 1,
	FWFP = 2,
};

const int N = 100010;
vector<pii> A[N];
int val[N];
int n;

pii dfs(int v)
{
	int ans0 = 0, ans10 = 0, ans11 = val[v], sum10 = 0;
	vector<pii> vec;
	for (auto [u, proto] : A[v]) {
		auto [x, y] = dfs(u); // x <= y
		ans0 += proto & FWFP? x: y;
		sum10 += proto & FWFP? x: y;
		ans11 += proto & FWP? x: y;
		vec.push_back({x, y});
	}
	Loop (i,0,A[v].size()) {
		auto [u, proto] = A[v][i];
		auto [x, y] = vec[i];
		sum10 -= proto & FWFP? x: y;
		sum10 += y;
		ans10 = max(ans10, sum10);
		sum10 -= y;
		sum10 += proto & FWP? x: y;
	}
	return {ans0, max(ans10, ans11)};
}

// Find out best sample
int findSample(int n, int confidence[], int host[], int protocol[])
{
	::n = n;
	Loop (i,1,n)
		A[host[i]].push_back({i, protocol[i]+1});
	Loop (i,0,n)
		val[i] = confidence[i];
	return dfs(0).second;
}

Compilation message

friend.cpp: In function 'pii dfs(int)':
friend.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
friend.cpp:31:2: note: in expansion of macro 'Loop'
   31 |  Loop (i,0,A[v].size()) {
      |  ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2660 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2660 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 1 ms 2656 KB Output is correct

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2656 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2792 KB Output is correct
6 Correct 3 ms 2672 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2660 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2656 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2660 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 1 ms 2660 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2788 KB Output is correct
10 Correct 3 ms 2788 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2664 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 1 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2660 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2664 KB Output is correct
3 Correct 3 ms 2648 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2660 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2648 KB Output is correct
10 Correct 2 ms 2660 KB Output is correct
11 Correct 2 ms 2656 KB Output is correct
12 Correct 39 ms 7252 KB Output is correct
13 Correct 20 ms 4964 KB Output is correct
14 Correct 35 ms 6756 KB Output is correct
15 Correct 34 ms 6736 KB Output is correct