Submission #225748

#	Time	Username	Problem	Language	Result	Execution time	Memory
225748		godwind	Mag (COCI16_mag)	C++14	96 / 120	610 ms	179136 KiB

mag

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <unordered_map>

using namespace std;

template<typename T> void uin(T &a, T b) {if (b < a) a = b;}
template<typename T> void uax(T &a, T b) {if (b > a) a = b;}

#define int long long
#define double long double
#define all(v) v.begin(), v.end()

const int N = 1000 * 1000 + 228;

vector<int> g[N];
int a[N];
int down[N], up[N];
int p[N];

void dfs(int v, int par = -1) {
	down[v] = (a[v] == 1);
	p[v] = par;
	for (int to : g[v]) {
		if (to != par) {
			dfs(to, v);
			if (a[v] == 1) uax(down[v], 1 + down[to]);
		}
	}
}

void jfs(int v, int par = -1) {
	if (a[v] == 1) uax(up[v], 1LL);
	if (par != -1 && a[v] == 1) uax(up[v], up[par] + 1);
	vector<int> sons;
	for (int to : g[v]) {
		if (to == par) continue;
		jfs(to, v);
		if (down[to] == 1) {
			sons.emplace_back(to);
		}
	}
	int mx1 = -100, mx2 = -100;
	for (int to : sons) {
		if (down[to] > mx1) {
			mx2 = mx1;
			mx1 = down[to];
		} else if (down[to] > mx2) mx2 = down[to];
	}
	for (int to : sons) {
		if (down[to] != mx1) {
			uax(up[to], mx1 + 2);
		} else uax(up[to], mx2 + 2);
	}
}

int P = 1500 * 1000 * 1000, Q = 1;

void relax(int pp, int qq) {
	if (pp * Q < P * qq) {
		P = pp;
		Q = qq;
	}
}

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

signed main() {
    ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}

	for (int i = 1; i <= n; ++i) cin >> a[i];
	dfs(1);
	jfs(1);
	for (int v = 1; v <= n; ++v) {
		relax(a[v], 1);
	}
	for (int v = 1; v <= n; ++v) {
		vector<int> values;
		for (int to : g[v]) {
			if (to != p[v] && a[to] == 1) {
				values.emplace_back(down[to]);
			}
		}
		if (p[v] != -1 && a[p[v]] == 1) values.emplace_back(up[p[v]]);
		sort(all(values));
		reverse(all(values));
		int len = 1;
		for (int i = 0; i < min(2LL, (int)values.size()); ++i) len += values[i];
		relax(a[v], len);
	}
	int G = gcd(P, Q);
	P/=G;
	Q/=G;
	cout << P << '/' << Q << '\n';
    return 0;
}
  
/*

Despite the fact that eating trash is very dangerous as a punishment, it remains effective way to reduce pollution.

The state of the environment is getting better during the quarantine.

Tote bags were totally banned in Sweden.

It's well known lots of famous actors support recycling and reuse of waste materials.

We have reached significant improvements regarding litter problem.

FTFTFFTFFTT
FTFFFFTFFTT
TTFTFFTFFTT
FTFTFTTFFTT





Eating trash is dangerous but 
И. Н. Сухих "Русская литература для всех."

Вопрос:
    Как Тургенев относился к Достоевскому и его творчеству?
Ответ: 
    Тургенев не любил Достоевского. Он считал, что тот использует дешевое средство под названием "обратное общее место"
для того, чтобы прослыть оригинальным писателем.

Вопрос:
    Почему Д.С.Лихачев называет Достоевского "самым непсихологическим писателем из всех существующих"?
Ответ:
    Потому что если подразумевать под психологией науку, то герои Достоевского в большинстве своем не подчиняются
    ее законам.
    Поведение его героев часто бывает непредсказуемо, они ведут себя неуравновешено (постоянно в бреду, лихорадке
    и падают в обморок).

Вопрос:
    Почему жанр романов Достоевского обычно определяют как идеалогический?
Ответ:
    Потому что герой Достоевского это прежде всего человек идеи, а не бытовой харакер или тип.

Вопрос:
    В чем особенность Петербурга Достоевского?
Ответ:
    Вопреки обычному представлению о Петербурге как о городе Невского проспекта и белых ночей, Петербург Достовевского - 
    это странный и местами страшный город, город "страшной жары" и "нестерпимой вони", со своими похожими на гроб
    каморками и множеством бедных, несчастных людей.

Вопрос:
    Являлись ли деньги основной причиной убийства старухи-процентщицы?
Ответ:
    Нет, не являлись. В 4 главе 5 части Раскольников признается Соне, что если бы он убил старуху лишь из-за голода,
    то он сейчас был бы счастлив. Основной причиной убийства была "проверка", принадлежит ли он высшему разряду 
    "законодателей человечества", как например Наполеон или такие ученые как Исаак Ньютон и Кеплер. Сможет ли он пойти
    (на убийство, вошь ли он или человек?

Вопрос:
    В чем схожесть Свидригайлова и Раскольникова?
Ответ:
    Во-первых оба они совершают преступления, только Свидригайлов прошел по пути Раскольникова много дальше. Они оба
    смогли заставить себя преступить кровавую черту и оба в конце испытывают сильнейшие муки совести и получают наказание.
    Душевные терзания Свидригайлова стали невыносимыми и он заканчивает жизнь самоубийством, Раскольников в итоге 
    сознается в содеянном и попадает на каторгу.

Вопрос:
    Соня - антипод или зеркало Раскольникова?
Ответ:
    С одной стороны есть очевидная схожесть между Соней и Раскольниковым - они оба переступили через границы нравственности.
    Но отличие в том, что Родион загубил чужую жизнь для себя, ради эксперимента, а Соня принесла себя в жертву
    ради семьи, у нее не было иного выхода.

Вопрос:
    В чем особенность эпилога "Преступления и наказания"?
Ответ:
    В романе "Преступление и наказанее" эпилог на закрывает историю полностью. Роман дает повод для рассуждений, но 
    имеет открытый концовку.

Вопрос:
    Какая связь "Преступления и наказания" с другим произведением Достоевеского "Двойники"?
Ответ:
    В "Преступлении и наказании" действительно прослеживается идея двойников. Двойник - это некоторое зеркало героя. 
    Мы можем видеть несколько двойников Раскольникова на протяжении романа, например до убийства он бедный и 
    безымянный студент в трактире, имеющий какие-то идеи убийства ради своеобразного блага, и после. Также "двойником"
    Раскольникова можно считать и следователя Порфирия Петровича - он очень хорошо разгадал дело Родиона, потому что
    узнал в его статье собственные мысли, которые после подавил. "Мне все эти ощущения знакомы, и статейку вашу я прочел
    как знакомую"

Вопрос:
    Кто автор работы, по которой писались вопросы/ответы?
Ответ:
    И.Н. Сухих - российский литературовед и критик, доктор филологических наук, профессор кафедры
    истории русской литературы СПбГУ

анаферон оциллококтиум




Для написания рецензии я выбрал фильм Альфреда Хичкока "Веревка"(1948). Этот фильм я смотрел с большим интересом, 
он цепляет с самого начала и держит в напряжении ближе к концу.
"Веревка" - это история о том, как двое приятелей - Брэндон и Филлип решили ради интереса воплотить в жизнь идею,
которую они обсуждали вместе со своим преподователем Рупертом. Идея заключалась в том, что люди разделяются
на два класса: "сверхлюди" - интеллектуальная элита, те люди, которые двигают, улучшают наш мир и 
"недолюди" - которые не отличаются талантом и интеллектом, жизнь которых глобально ничего не значит и ни на что не влияет.
Суть была в том, что убийство является привилегией "высших людей", что они могут иногда убивать "низших", если те
являются помехой. Все это было описано Ницше в его теории о "Сверхчеловеке" и так же знакомо нам из
"Преступления и наказания", где схожие мысли были у Родиона Раскольникова. Брэндон и Филлип, проникшись этими идеями и 
возомнив себя интеллектуальной элитой общества, решили, что нужно переносить эту теорию со страниц книг и обсуждений с
учителем в реальную жизнь, решив провести эксперимент. Таким образом фильм начинается с удушения ими Девида Кентли. Они
прячут его тело в сундук из под книг и накрывают на нем стол. Вскоре приходят гости,
в том числе и Руперт Кэделл, при котором оба из них начинают нервничать, что в конечном итоге их и выдает. Все это 
происходит постепенно, вперемешку с разговорами, шутками, и даже выяснением личных отношений между Джанет и Кеннетом.
В итоге, с течением времени Руперт начинает понимать, что проиходит и в конце он находит в сундуке тело мертвого Девида.
Брэндон пытается найти понимание учителя в том, что они решили воплотить его теорию, но Руперт дал понять, что его слова
значили совсем не то, и что убийство Девида был ужасным и бессердечным поступком. Руперт несколько раз стреляет в окно
из револьвера, привлекая этим внимание окружающих и полиции, тем самым за совершенным ими преступлением последует
серьезное наказание. Дальнейшая судьба героев картины нам неизвестна, поэтому финал остается открытым, аналогично эпилогу
"Преступления и наказания" у Достоевского.

"Веревка" - хороший пример того, как имея минимальное количество декораций можно создать остросюжетный фильм, который
будет держать в напряжении до самого конца.































*/

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