# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
583454 |
2022-06-25T11:29:05 Z |
thezomb1e |
Friend (IOI14_friend) |
C++17 |
|
188 ms |
65536 KB |
#include "friend.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define pb push_back
#define ft first
#define sd second
#define pi pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(...) dbg_out(__VA_ARGS__)
using ll = long long;
using ld = long double;
using namespace std;
//Constants
const ll INF = 5 * 1e18;
const int IINF = 2 * 1e9;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ld PI = 3.14159265359;
template<typename T> void mins(T& x, T y) {x = min(x, y);}
template<typename T> void maxs(T& x, T y) {x = max(x, y);}
vector<vector<int>> e;
vector<int> a;
int subtask1() {
int n = a.size();
int ans = 0;
for (int mask = 0; mask < (1 << n); mask++) {
bool ok = true;
int cur = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
cur += a[i];
for (int to : e[i]) {
if (mask & (1 << to)) {
ok = false;
}
}
}
}
if (ok) maxs(ans, cur);
}
return ans;
}
int subtask2() {
int ans = 0;
for (int x : a) {
ans += x;
}
return ans;
}
int subtask3() {
int ans = 0;
for (int x : a) {
maxs(ans, x);
}
return ans;
}
int subtask4() {
int ans = 0;
int n = a.size();
vector<bool> vis(n + 5, false);
vector<vector<int>> dp(n + 5, vector<int> (2, 0));
function<void(int)> dfs = [&](int f) {
vis[f] = true;
dp[f][1] += a[f];
for (int to : e[f]) {
if (!vis[to]) {
dfs(to);
dp[f][0] += max(dp[to][1], dp[to][0]);
dp[f][1] += dp[to][0];
}
}
};
for (int i = 0; i < n; i++) {
if (!vis[i]) {
dfs(i);
ans += max(dp[i][0], dp[i][1]);
}
}
return ans;
}
// Find out best sample
int findSample (int n, int confidence[], int host[],int protocol[]){
e.resize(n + 5); a.resize(n);
for (int i = 0; i < n; i++)
a[i] = confidence[i];
bool sub1, sub2, sub3, sub4;
sub1 = sub2 = sub3 = sub4 = true;
for (int i = 1; i < n; i++) {
sub2 &= protocol[i] == 1;
sub3 &= protocol[i] == 2;
sub4 &= protocol[i] == 0;
if (protocol[i] == 0) {
e[host[i]].pb(i);
e[i].pb(host[i]);
} else if (protocol[i] == 1) {
for (int to : e[host[i]]) {
e[to].pb(i);
e[i].pb(to);
}
} else {
for (int to : e[host[i]]) {
e[to].pb(i);
e[i].pb(to);
}
e[host[i]].pb(i);
e[i].pb(host[i]);
}
}
sub1 &= n <= 10;
if (sub1) return subtask1();
else if (sub2) return subtask2();
else if (sub3) return subtask3();
else if (sub4) return subtask4();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 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 |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
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 |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 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 |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1108 KB |
Output is correct |
2 |
Correct |
9 ms |
4180 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
6 ms |
3028 KB |
Output is correct |
5 |
Correct |
9 ms |
4052 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
2 ms |
1108 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
10 ms |
4336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
468 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 |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
312 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
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 |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
316 KB |
Output is correct |
11 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 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 |
296 KB |
Output is correct |
6 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Runtime error |
188 ms |
65536 KB |
Execution killed with signal 9 |
13 |
Halted |
0 ms |
0 KB |
- |