oj.uz

답안 #83690

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
83690 2018-11-09T21:53:35 Z jasony123123 Mag (COCI16_mag) C++11
0 / 120
 3 ms 1416 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>;

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

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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 764 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1184 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #6
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -