oj.uz

답안 #53871

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53871 2018-07-01T13:11:52 Z baactree Islands (IOI08_islands) C++17
0 / 100
 640 ms 225948 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct SGT {
	vector<ll> tree;
	int sz;
	SGT(int n) {
		sz = 1;
		while (sz < n)sz *= 2;
		tree.resize(sz * 2);
	}
	ll query(int le, int ri) {
		le += sz;
		ri += sz;
		ll ret = 0;
		while (le <= ri) {
			if (le & 1)ret = max(ret, tree[le++]);
			if (!(ri & 1))ret = max(ret, tree[ri--]);
			le /= 2;
			ri /= 2;
		}
		return ret;
	}
};
int n;
vector<tuple<int,int,int> > adj[1000005];
int trip[1000005], w[1000005];
bool chk[1000005], chk2[1000005];
vector<int> cycle,len;
ll ds[1000005], dd[1000005];
vector<ll> d;
int r[1000005];
int vn;
void dfs(int now, int pi) {
	r[now] = trip[now] = ++vn;
	for (auto &e : adj[now]) {
		if (get<1>(e)==pi)continue;
		if (!trip[get<0>(e)]) {
			dfs(get<0>(e), get<1>(e));
			r[now] = min(r[now], r[get<0>(e)]);
		}
		else if(!chk[get<0>(e)]){
			r[now] = min(r[now], trip[get<0>(e)]);
			cycle.push_back(get<0>(e));
			chk[get<0>(e)] = true;
			len.push_back(w[get<1>(e)]);
		}
	}
	if (r[now] < trip[now]) {
		chk[now] = true;
		cycle.push_back(now);
		len.push_back(w[pi]);
	}
}
ll val;
void dfs2(int now) {
	chk[now] = true;
	for (auto &e : adj[now]) {
		if (chk[get<0>(e)])continue;
		dfs2(get<0>(e));
		val = max(val, dd[now] + dd[get<0>(e)] + get<1>(e));
		dd[now] = max(dd[now], dd[get<0>(e)] + get<1>(e));
	}
}
ll calc(vector<ll> &d, vector<int> &len, int m) {
	for (int i = 1; i < m; i++)
		ds[i] = ds[i - 1] + len[i - 1];
	SGT sgt(m * 2);
	ll sum = len[0];
	for (int i = 1; i < m * 2; i++) {
		sgt.tree[i + sgt.sz] = sum + d[i%m];
		sum += len[i%m];
	}
	for (int i = sgt.sz - 1; i; i--)
		sgt.tree[i] = max(sgt.tree[i * 2], sgt.tree[i * 2 + 1]);
	ll ret = 0;
	for (int i = 0; i < m; i++) {
		ll temp = d[i] + sgt.query(i + 1, i + m - 1) - ds[i];
		ret = max(ret, temp);
	}
	return ret;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		adj[i].emplace_back(a, b, i);
		adj[a].emplace_back(i, b, i);
		w[i] = b;
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		if (!trip[i]) {
			cycle.clear();
			len.clear();
			dfs(i, 0);
			int m = cycle.size();
			d = vector<ll>(m);
			val = 0;
			for (int i = 0; i < cycle.size(); i++) {
				dfs2(cycle[i]);
				d[i] = dd[cycle[i]];
			}
			val = max(val,calc(d, len, m));
			reverse(len.begin(), len.end() - 1);
			reverse(d.begin(), d.end());
			val = max(val, calc(d, len, m));
			ans += val;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:101:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < cycle.size(); i++) {
                    ~~^~~~~~~~~~~~~~
islands.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
islands.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 45 ms 47488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 21 ms 47668 KB Output isn't correct
3 Runtime error 48 ms 47668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 50 ms 47748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 49 ms 47752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 49 ms 47800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 52 ms 47844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 49 ms 47844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 48 ms 47884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 48 ms 47964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 47 ms 47964 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 3.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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