| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 299623 | kevlee | Friend (IOI14_friend) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
#define h1 7897897897897897
#define h2 7897466719774591
#define b1 98762051
#define b2 98765431
#define inf 1000000000
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a))
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
vi edges[100005];
int dp[100005][2], a[100005], color[100005], one, two;
void dfs(int x, int p) {
dp[x][1] = a[x];
for (auto y: edges[x]) {
if (y != p) {
dfs(y, x);
dp[x][1] += dp[y][0];
dp[x][0] += max(dp[y][0], dp[y][1]);
}
}
}
void dfs_color(int x, int p, int c) {
color[x] = c;
if (c == 1) one++;
else two++;
for (auto y: edges[x]) {
if (y != p) {
dfs_color(y, x, 3-c);
}
}
}
int subtask5() {
int res = 0;
FOR(i, 0, n-1) {
if (!color[i]) {
one = two = 0;
dfs_color(i, -1, 1);
res += max(one, two);
}
}
return res;
}
int findSample(int n,int confidence[],int host[],int protocol[]){
FOR(i, 0, n-1) a[i] = confidence[i];
FOR(i, 1, n-1) {
if (protocol[i] == 0) {
edges[i].pb(host[i]);
edges[host[i]].pb(i);
} else if (protocol[i] == 1) {
for (auto y: edges[host[i]]) {
edges[i].pb(y);
edges[y].pb(i);
}
} else {
for (auto y: edges[host[i]]) {
edges[i].pb(y);
edges[y].pb(i);
}
edges[i].pb(host[i]);
edges[host[i]].pb(i);
}
}
if (*max_element(a, a+n) == 1) {
return subtask5();
}
dfs(0, -1);
return max(dp[0][0], dp[0][1]);
}