Submission #1182570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182570		sano	Friend (IOI14_friend)	C++20	16 / 100	1 ms	328 KiB

friend

//#pragma GCC optimize("O3")
//#pragma GCC target("tune=native")
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include "friend.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define shit short int
#define ll long long
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define NEK 2000000000
#define mod 998244353
#define mod2 1000000009
#define rsz resize
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;
//using namespace __gnu_pbds;

//template <typename T1, typename T2>
//using indexed_set = tree<pair<T1, T2>, null_type, less<pair<T1, T2>>, rb_tree_tag, tree_order_statistics_node_update>;

vec<vec<int>> g;
vec<int> dp1, dp2;

void daj(int x, int c[]) {
	int suc1 = 0, suc2 = 0;
	for (auto i : g[x]) {
		daj(i, c);
		suc1 += dp1[i];
		suc2 += dp2[i];
	}
	dp1[x] = max(suc1, suc2 + c[x]);
	dp2[x] = suc1;
	return;
}

int vyries_strom(int n, int c[], int host[]) {
	g.resize(n);
	dp1.resize(n);
	dp2.resize(n);
	ffor(i, 1, n) {
		g[host[i]].push_back(i);
	}
	daj(0, c);
	return dp1[0];
}

int findSample(int n, int c[], int host[], int protocol[]) {
	if (n <= 10) {
		vec<set<int>> gg(n);
		ffor(i, 1, n) {
			if (protocol[i] == 0) {
				gg[host[i]].insert(i);
				gg[i].insert(host[i]);
			}
			if (protocol[i] == 1) {
				for (auto j : gg[host[i]]) {
					gg[i].insert(j);
					gg[j].insert(i);
				}
			}
			if (protocol[i] == 2) {
				for (auto j : gg[host[i]]) {
					gg[i].insert(j);
					gg[j].insert(i);
				}
				gg[host[i]].insert(i);
				gg[i].insert(host[i]);
			}
		}
		int maxi = 0;
		For(i, (1 << n)) {
			bool zle = 0;
			int suc = 0;
			For(j, n) {
				suc += c[j];
				if ((i & (1 << j))) {
					for (auto k : gg[j]) {
						if ((i & (1 << k))) zle = 1;
					}
				}
			}
			if (zle) continue;
			maxi = max(maxi, suc);
		}
		return maxi;
	}
	bool rovnake = 1;
	int pr = protocol[1];
	ffor(i, 1, n) {
		if (protocol[i] != pr) rovnake = 0;
	}
	if (rovnake) {
		if (pr == 0) {
			return vyries_strom(n, c, host);
		}
		if (pr == 1) {
			int suc = 0;
			For(i, n) {
				suc += c[i];
			}
			return suc;
		}
		if (pr == 2) {
			int maxi = 0;
			For(i, n) {
				maxi = max(maxi, c[i]);
			}
			return maxi;
		}
	}
	return 1;
}
/*
signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int t;
	t = 1;
	For(i, t) {

	}
	return 0;
}*/

• Subtask 1: 0 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31