oj.uz

Submission #548424

# Submission time Handle Problem Language Result Execution time Memory
548424 2022-04-13T10:24:39 Z Temmie Islands (IOI08_islands) C++17
50 / 100
 2000 ms 131072 KB 
#include <bits/stdc++.h>

struct Seg {
	
	std::vector <long long> v, w;
	int size;
	
	Seg(int s) {
		size = 1;
		while (size < s) {
			size <<= 1;
		}
		v.resize(size << 1, 0);
		w.resize(size << 1, 0);
	}
	
	void update(int l, int r, long long delta) {
		update(l, r, delta, 0, 0, size);
	}
	
	void update(int tl, int tr, long long delta, int now, int l, int r) {
		if (l >= tr || r <= tl) {
			return;
		}
		if (l >= tl && r <= tr) {
			w[now] += delta;
			return;
		}
		push(now, l, r);
		int mid = (l + r) >> 1;
		update(tl, tr, delta, now * 2 + 1, l, mid);
		update(tl, tr, delta, now * 2 + 2, mid, r);
	}
	
	long long query(int l, int r) {
		return query(l, r, 0, 0, size);
	}
	
	long long query(int tl, int tr, int now, int l, int r) {
		if (l >= tr || r <= tl) {
			return 0;
		}
		push(now, l, r);
		if (l >= tl && r <= tr) {
			return v[now];
		}
		int mid = (l + r) >> 1;
		return std::max(query(tl, tr, now * 2 + 1, l, mid), query(tl, tr, now * 2 + 2, mid, r));
	}
	
	void push(int node, int l, int r) {
		v[node] += w[node] * (r - l);
		if (r - l - 1) {
			w[node * 2 + 1] += w[node];
			w[node * 2 + 2] += w[node];
		}
		w[node] = 0;
	}
	
};

int n;
std::vector <std::vector <std::pair <int, std::pair <int, int>>>> g;
std::vector <std::vector <int>> c;
std::vector <int> cc;
std::vector <long long> cans;

void fc(int node, std::vector <bool>& vis) {
	if (vis[node]) {
		return;
	}
	vis[node] = true;
	c.back().push_back(node);
	for (auto p : g[node]) {
		fc(p.second.first, vis);
	}
}

std::vector <bool> cyc;

bool cy(int node, int par, std::vector <bool>& vis) {
	if (vis[node]) {
		return cyc[node] = true;
	}
	vis[node] = true;
	for (auto p : g[node]) {
		if (p.first != par && cy(p.second.first, p.first, vis)) {
			return cyc[node] ? false : (cyc[node] = true);
		}
	}
	return false;
}

long long td(int node, int par = -1) {
	std::vector <long long> ch;
	for (auto p : g[node]) {
		if (p.second.first == par || cyc[p.second.first]) {
			continue;
		}
		ch.push_back(td(p.second.first, node) + p.second.second);
	}
	std::sort(ch.rbegin(), ch.rend());
	if (ch.size()) {
		cans[cc[node]] =
		std::max(cans[cc[node]], (int) ch.size() > 1 ? ch[0] + ch[1] : ch.empty() ? 0LL : ch[0]);
	}
	return ch.size() ? ch[0] : 0LL;
}

std::vector <long long> sus;

void gse(int node, int par, std::vector <bool>& vis, std::vector <std::pair <long long, long long>>& seq) {
	for (auto p : g[node]) {
		if (p.second.first != par && cyc[p.second.first] && !vis[p.second.first]) {
			vis[p.second.first] = true;
			seq.emplace_back(sus[p.second.first], p.second.second);
			gse(p.second.first, node, vis, seq);
		}
	}
}

int main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0);
	
	std::cin >> n;
	g.resize(n);
	for (int i = 0; i < n; i++) {
		int u, w; std::cin >> u >> w; u--;
		g[u].push_back({ i, { i, w } });
		g[i].push_back({ i, { u, w } });
	}
	std::vector <bool> vis(n, false);
	cc.resize(n, -1);
	for (int i = 0; i < n; i++) {
		if (vis[i]) {
			continue;
		}
		c.resize(c.size() + 1);
		cans.resize(cans.size() + 1, 0);
		fc(i, vis);
		for (int x : c.back()) {
			cc[x] = (int) c.size() - 1;
		}
	}
	cyc.resize(n, false);
	vis = std::vector <bool> (n, false);
	for (auto& v : c) {
		cy(v[0], -1, vis);
	}
	sus.resize(n, 0);
	for (int i = 0; i < n; i++) {
		if (cyc[i]) {
			sus[i] = td(i);
		}
	}
	vis = std::vector <bool> (n, false);
	for (int i = 0; i < n; i++) {
		if (!vis[i] && cyc[i]) {
			std::vector <std::pair <long long, long long>> seq;
			gse(i, -1, vis, seq);
			if ((int) seq.size() < 2) {
				seq.clear();
				for (int x : c[cc[i]]) {
					if (cyc[x]) {
						for (auto p : g[x]) {
							if (cyc[p.second.first]) {
								seq.emplace_back(sus[p.second.first], p.second.second);
							}
						}
					}
				}
				std::sort(seq.begin(), seq.end(), [] (
				std::pair <long long, long long> u, std::pair <long long, long long> v) {
					return u.second < v.second;
				});
				seq = { seq.front(), seq.back() };
			}
			int m = seq.size();
			//for (int k = 0; k < 2; k++) {
				//Seg seg(m);
				//long long sum = 0;
				//for (int j = 0; j < m; j++) {
					//seg.update(j, j + 1, seq[j].first + (sum += seq[j].second));
				//}
				//for (int j = 0; j < m; j++) {
					//seg.update(j + 1, m, -seq[j].second);
					//cans[cc[i]] = std::max(cans[cc[j]], seg.query(0, m));
					//seg.update(0, m, seq[0].second);
				//}
				//long long tmp = seq[0].second;
				//for (int j = 1; j < m; j++) {
					//seq[j - 1].second = seq[j].second;
				//}
				//seq[m - 1].second = tmp;
				//std::reverse(seq.begin(), seq.end());
			//}
			for (int j = 0; j < m; j++) {
				long long sum = seq[j].first;
				for (int k = 1; k < m; k++) {
					int ind = (j + k) % m;
					cans[cc[i]] = std::max(cans[cc[i]], (sum += seq[ind].second) + seq[ind].first);
				}
			}
		}
	}
	long long ans = 0;
	for (long long x : cans) {
		ans += x;
	}
	std::cout << ans << "\n";
	
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 23 ms 844 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 2044 KB Output is correct
2 Correct 1119 ms 5372 KB Output is correct
3 Correct 12 ms 2388 KB Output is correct
4 Correct 6 ms 1352 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1974 ms 7536 KB Output is correct
2 Execution timed out 2017 ms 11680 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2024 ms 19964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2055 ms 34784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 101652 KB Output is correct
2 Runtime error 738 ms 131072 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 384 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -