oj.uz

Submission #118355

# Submission time Handle Problem Language Result Execution time Memory
118355 2019-06-18T17:17:21 Z eriksuenderhauf Islands (IOI08_islands) C++11
100 / 100
 955 ms 106248 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const ll INF = 1e18 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
int par[MAXN], w[MAXN], deg[MAXN];
vi adj[MAXN];
ll dp[MAXN], pre[MAXN], depth[MAXN];

ll diam(int u) {
	ll mx1 = 0, mx2 = 0;
	for (int v: adj[u]) {
		if (mx1 < depth[v] + w[v]) {
			mx2 = mx1;
			mx1 = depth[v] + w[v];
		} else if (mx2 < depth[v] + w[v])
			mx2 = depth[v] + w[v];
	}
	return mx1 + mx2;
}

int main() {
	int n;
	ni(n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &par[i], &w[i]);
		deg[par[i]]++;
		adj[par[i]].pb(i);
	}
	deque<int> pq;
	for (int i = 1; i <= n; i++)
		if (deg[i] == 0)
			pq.pb(i);
	while (!pq.empty()) {
		int u = pq.front(); pq.pop_front();
		dp[u] = max(dp[u], diam(u));
		dp[par[u]] = max(dp[par[u]], dp[u]);
		depth[par[u]] = max(depth[par[u]], depth[u] + w[u]);
		if (--deg[par[u]] == 0)
			pq.pb(par[u]);
		par[u] = 0;
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		if (par[i] == 0)
			continue;
		ll sm = 0, m1 = -INF, m2 = -INF, cur = 0;
		vll act;
		act.pb(mp(0, 0));
		int u = i;
		while (par[u] != 0) {
			act.pb(mp(depth[u], w[u]));
			cur = max(cur, max(dp[u], diam(u)));
			sm += w[u];
			int nx = u;
			u = par[u];
			par[nx] = 0;
		}
		for (int i = 1; i < act.size(); i++)
			pre[i] = pre[i - 1] + act[i].se;
		for (int i = 1; i < act.size(); i++) {
			cur = max(cur, max(act[i].fi + pre[i - 1] + m1, act[i].fi + sm - pre[i - 1] + m2));
			m1 = max(m1, act[i].fi - pre[i - 1]);
			m2 = max(m2, act[i].fi + pre[i - 1]);
		}
		ans += cur;
	}
	prl(ans);
    return 0;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < act.size(); i++)
                   ~~^~~~~~~~~~~~
islands.cpp:92:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < act.size(); i++) {
                   ~~^~~~~~~~~~~~
islands.cpp:9:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
islands.cpp:55:2: note: in expansion of macro 'ni'
  ni(n);
  ^~
islands.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &par[i], &w[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct
2 Correct 21 ms 23936 KB Output is correct
3 Correct 22 ms 23936 KB Output is correct
4 Correct 21 ms 23780 KB Output is correct
5 Correct 23 ms 23808 KB Output is correct
6 Correct 21 ms 23808 KB Output is correct
7 Correct 23 ms 23932 KB Output is correct
8 Correct 30 ms 23936 KB Output is correct
9 Correct 23 ms 23808 KB Output is correct
10 Correct 22 ms 23800 KB Output is correct
11 Correct 22 ms 23808 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23936 KB Output is correct
2 Correct 24 ms 24192 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24696 KB Output is correct
2 Correct 39 ms 26204 KB Output is correct
3 Correct 31 ms 25088 KB Output is correct
4 Correct 27 ms 24448 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 26612 KB Output is correct
2 Correct 60 ms 30352 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 33648 KB Output is correct
2 Correct 105 ms 40772 KB Output is correct
3 Correct 120 ms 43756 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 42984 KB Output is correct
2 Correct 199 ms 55936 KB Output is correct
3 Correct 213 ms 65492 KB Output is correct
4 Correct 262 ms 67780 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 47676 KB Output is correct
2 Correct 635 ms 75316 KB Output is correct
3 Correct 309 ms 64888 KB Output is correct
4 Correct 377 ms 82464 KB Output is correct
5 Correct 381 ms 81052 KB Output is correct
6 Correct 955 ms 74748 KB Output is correct
7 Correct 387 ms 94664 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 82552 KB Output is correct
2 Correct 410 ms 97920 KB Output is correct
3 Correct 394 ms 106248 KB Output is correct
4 Correct 425 ms 82032 KB Output is correct
5 Correct 363 ms 90976 KB Output is correct
6 Correct 397 ms 88696 KB Output is correct
7 Correct 935 ms 86520 KB Output is correct