oj.uz

Submission #312174

# Submission time Handle Problem Language Result Execution time Memory
312174 2020-10-12T14:49:59 Z Akashi Islands (IOI08_islands) C++14
80 / 100
 1236 ms 131076 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define x first
#define y second
 
const int DIM = 1e6 + 1;
 
int n;
long long ans;
bool viz[DIM];
int tt[DIM], ct[DIM];
long long s[DIM], dp[DIM], sp[DIM], mx[DIM];
 
vector <pair <int, int>> v[DIM];
 
int nr;
pair <int, int> cyc[DIM];
bool onCyc[DIM];
 
bool find_cycle(int nod) {
	viz[nod] = true;
	
	bool found = false;
	bool foundPapa = false;
	for (auto it : v[nod]) {
		if (it.x == tt[nod] && !foundPapa) {
			foundPapa = true;
			continue ;
		}
 
		if (!found && viz[it.x]) {
			int now = nod;
			
			while (now != tt[it.x]) {
				if (now != it.x) cyc[++nr] = {now, ct[now]};
				else cyc[++nr] = {now, it.y};
				onCyc[now] = true;
				now = tt[now];
			}
			found = true;
			continue ;
		}
 
		if (viz[it.x]) continue ;
		
		ct[it.x] = it.y; tt[it.x] = nod;
		bool ok = find_cycle(it.x);
		found |= ok;
	}
 
	return found;
}
 
void dfs(int nod, int papa = 0) {
	for (auto it : v[nod]) {
		if (onCyc[it.x] || it.x == papa) continue ;
		dfs(it.x, nod);
		ans = max(ans, dp[nod] + dp[it.x] + it.y);
		dp[nod] = max(dp[nod], dp[it.x] + it.y);
	}
}
 
int main() {
	scanf("%d", &n);
	int x, y;
	for (int i = 1; i <= n ; ++i) {
		scanf("%d%d", &x, &y);
 
		v[i].push_back({x, y});
		v[x].push_back({i, y});
	}
 
	long long sol = 0;
	for (int i = 1; i <= n ; ++i) {
		if (viz[i]) continue ;
		nr = 0; ans = 0;
		find_cycle(i);
		
		long long sum = 0;
		for (int i = 1; i <= nr ; ++i) {
			int nod = cyc[i].x;
			sp[nod] = sum;
			for (auto it : v[nod]) {
				if (!onCyc[it.x]) {
					dfs(it.x);
					ans = max(ans, mx[nod] + dp[it.x] + it.y);
					mx[nod] = max(mx[nod], dp[it.x] + it.y);
				}
			}
			s[nod] = mx[nod] + sp[nod];
			sum = sum + cyc[i].y;
			ans = max(ans, mx[nod]);
		}
 
		for (int i = nr - 1; i >= 1 ; --i) {
			int nod = cyc[i].x;
			ans = max(ans, mx[nod] - sp[nod] + s[cyc[i + 1].x]);
			s[nod] = max(s[nod], s[cyc[i + 1].x]);
		}
		
		for (int i = 1; i <= nr ; ++i) {
			int nod = cyc[i].x;
			s[nod] = mx[nod] + sum - sp[nod];
		}
		
		for (int i = nr - 1; i >= 1 ; --i) {
			int nod = cyc[i].x;
			ans = max(ans, mx[nod] + sp[nod] + s[cyc[i + 1].x]);
			s[nod] = max(s[nod], s[cyc[i + 1].x]);
		}
		
 
		sol += ans;
	}
 
	printf("%lld\n", sol);
 
	return 0;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
islands.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 15 ms 23936 KB Output is correct
3 Correct 15 ms 23936 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 15 ms 23808 KB Output is correct
6 Correct 15 ms 23808 KB Output is correct
7 Correct 15 ms 23808 KB Output is correct
8 Correct 15 ms 23808 KB Output is correct
9 Correct 16 ms 23808 KB Output is correct
10 Correct 15 ms 23808 KB Output is correct
11 Correct 16 ms 23808 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24064 KB Output is correct
2 Correct 17 ms 24320 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25216 KB Output is correct
2 Correct 38 ms 27776 KB Output is correct
3 Correct 28 ms 25464 KB Output is correct
4 Correct 21 ms 24696 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 29176 KB Output is correct
2 Correct 61 ms 31992 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 40824 KB Output is correct
2 Correct 120 ms 41720 KB Output is correct
3 Correct 147 ms 52088 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 53372 KB Output is correct
2 Correct 248 ms 77436 KB Output is correct
3 Correct 266 ms 75768 KB Output is correct
4 Correct 341 ms 96120 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 72016 KB Output is correct
2 Correct 909 ms 131072 KB Output is correct
3 Correct 387 ms 95740 KB Output is correct
4 Correct 493 ms 131072 KB Output is correct
5 Correct 478 ms 131072 KB Output is correct
6 Correct 1236 ms 96376 KB Output is correct
7 Runtime error 510 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 520 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -