oj.uz

Submission #83696

# Submission time Handle Problem Language Result Execution time Memory
83696 2018-11-09T22:24:08 Z jasony123123 Mag (COCI16_mag) C++11
120 / 120
 1427 ms 199360 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35576 KB Output is correct
2 Correct 33 ms 35580 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 35648 KB Output is correct
2 Correct 33 ms 35648 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1147 ms 100636 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 100636 KB Output is correct
2 Correct 1307 ms 169564 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1401 ms 169564 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1218 ms 169564 KB Output is correct
2 Correct 915 ms 169564 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1279 ms 169564 KB Output is correct
2 Correct 188 ms 169564 KB Output is correct
3 Correct 1427 ms 199360 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 199360 KB Output is correct
2 Correct 1253 ms 199360 KB Output is correct
3 Correct 830 ms 199360 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1157 ms 199360 KB Output is correct
2 Correct 1290 ms 199360 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1308 ms 199360 KB Output is correct
2 Correct 818 ms 199360 KB Output is correct