Submission #83690

#	Time	Username	Problem	Language	Result	Execution time	Memory
83690		jasony123123	Mag (COCI16_mag)	C++11	0 / 120	3 ms	1416 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>;

ll __gcd(ll x, ll y)
{
	if (x < y)
		return __gcd(y, x);
	if (y == 0)
		return x;
	else
		return __gcd(y, x%y);
}

struct rational {
	ll p, q;
	rational(ll a, ll b) {
		ll g = __gcd(a, b);
		p = a / g;
		q = b / g;
	}
	bool operator < (const rational& rr) const {
		return rr.q*p < rr.p < q;
	}
	bool operator > (const rational& rr) const {
		return rr.q*p > rr.p < q;
	}
};

const int MAXN = 100;
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);
		dfsone(c, x);
	}
	dpone[x] = q + w;
}
void dfsup(int x, int p) {
	if (p != -1 && magic[p] == 1) {
		dpup[x] = dpup[p];
		for (int s : adj[p]) if (s != x)
			dpup[x] = max(dpdown[s], dpup[x]);
		dpup[x]++;
	}
	for (int c : adj[x]) if (c != p)
		dfsup(c, x);
}
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] += 1;
	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);
	dfsdown(1, -1);
	dfsup(1, -1);
	dfsone(1, -1);

	// find ans
	rational ans(magic[1], dpone[1] + 1);
	FORE(i, 1, N) {
		rational con(magic[i], dpone[i] + 1);
		if (con > ans)
			ans = con;
	}
	cout << ans.p << "/" << ans.q << "\n";
	return 0;
}

Compilation message (stderr)

mag.cpp: In member function 'bool rational::operator<(const rational&) const':
mag.cpp:41:17: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
   return rr.q*p < rr.p < q;
          ~~~~~~~^~~~~~
mag.cpp: In member function 'bool rational::operator>(const rational&) const':
mag.cpp:44:17: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
   return rr.q*p > rr.p < q;
          ~~~~~~~^~~~~~

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