Submission #83696

#	Time	Username	Problem	Language	Result	Execution time	Memory
83696		jasony123123	Mag (COCI16_mag)	C++11	120 / 120	1427 ms	199360 KiB

mag

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define vsort(a) sort(a.begin(), a.end());
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf

typedef long long ll;
typedef pair<int, int > pii;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

bool isbigger(pair<ll, ll> &a, pair<ll, ll> &b) {
	ll g1 = __gcd(a.first, a.second);
	ll g2 = __gcd(b.first, b.second);
	a.first /= g1, a.second /= g1, b.first /= g2, b.second /= g2;
	return b.second*a.first > b.first*a.second;
}

const int MAXN = 1000010;
int N;
v<int> adj[MAXN];
ll magic[MAXN];
int dpdown[MAXN], dpup[MAXN], dpone[MAXN];

void dfsone(int x, int p) {
	int q = dpup[x], w = 0, e = 0; // >=
	for (auto c : adj[x]) if (c != p) {
		e = dpdown[c];
		if (w < e) swap(w, e);
		if (q < w) swap(q, w);
		assert(q >= w && w >= e);
		dfsone(c, x);
	}
	dpone[x] = q + w;
}
void dfsup(int x, int p,  int g) {
	if (p != -1 && magic[p] == 1) {
		dpup[x] = dpup[p];
		for (int s : adj[p]) if (s != x && s!=g)
			dpup[x] = max(dpdown[s], dpup[x]);
		dpup[x]++;
	}
	for (int c : adj[x]) if (c != p)
		dfsup(c, x, p);
}
int dfsdown(int x, int p) {
	for (int c : adj[x]) if (c != p)
		dpdown[x] = max(dpdown[x], dfsdown(c, x));
	if (magic[x] != 1)
		dpdown[x] = 0;
	else
		dpdown[x]++;
	return dpdown[x];
}
int main() {
	
	// input
	cin >> N;
	FOR(i, 0, N - 1) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	FORE(i, 1, N)
		cin >> magic[i];

	// init and compute dp
	memset(dpdown, 0, sizeof dpdown);
	memset(dpup, 0, sizeof dpup);
	memset(dpone, 0, sizeof dpone);
	dfsdown(1, -1);
	dfsup(1, -1, -1);
	dfsone(1, -1);

	// find ans
	pair<ll, ll> ans(magic[1], dpone[1] + 1);
	FORE(i, 1, N) {
		pair<ll, ll> cmp(magic[i], dpone[i] + 1);
		if (isbigger(ans, cmp))
			ans = cmp;
	}
	cout << ans.first << "/" << ans.second << "\n";
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12