oj.uz

Submission #120393

# Submission time Handle Problem Language Result Execution time Memory
120393 2019-06-24T10:38:05 Z nvmdava Islands (IOI08_islands) C++17
100 / 100
 862 ms 131072 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
#define N 1000005

pair<int, int> to[N];
vector<int> from[N];
bool inCyc[N];
bool in[N];
vector<int> cyc;
long long res, ans, tp, tmm;
vector<long long> p, dp;
void trav(int i){
	in[i] = 1;
	cyc.push_back(i);
	if(in[to[i].ff]){
		bool ok = 0;
		for(int& x : cyc){
			if(x == to[i].ff)ok = 1;
			if(ok)inCyc[x] = 1;
		}
	} else trav(to[i].ff);
	cyc.pop_back();
}
long long dfs(int v){
	long long b1 = 0, b2 = 0;
	for(int& x : from[v]){
		if(inCyc[x]) continue;
		long long up = dfs(x) + to[x].ss;
		if(up > b1){
			b2 = b1;
			b1 = up;
		} else b2 = max(b2, up);
	}
	res = max(res, b1 + b2);
	return b1;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	
	for(int i = 1; i <= n; i++){
		cin>>to[i].ff>>to[i].ss;
		from[to[i].ff].push_back(i);
	}
	
	for(int i = 1; i <= n; i++){
		if(in[i]) continue;
		trav(i);
	}
	for(int i = 1; i <= n; i++){
		if(inCyc[i]){
			res = 0;
			cyc.clear();
			p.clear();
			dp.clear();
			int t = i;
			p.push_back(0);
			do {
				cyc.push_back(t);
				p.push_back(p.back() + to[t].ss);
				dp.push_back(dfs(t));
				t = to[t].ff;
			} while (cyc[0] != t);
			for(int x : cyc) inCyc[x] = 0;
			tmm = dp[0] - p[0];
			tp = dp[0] + p[0];
			for(int i = 1; i < cyc.size(); i++){
				res = max(res, dp[i] + p[i] + tmm);
				res = max(res, dp[i] - p[i] + tp + p.back());
				tmm = max(tmm, dp[i] - p[i]);
				tp = max(tp, dp[i] + p[i]);
			}
			ans += res;
		}
	}
	cout<<ans;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:73:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 1; i < cyc.size(); i++){
                   ~~^~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 23800 KB Output is correct
2 Correct 23 ms 23936 KB Output is correct
3 Correct 22 ms 23936 KB Output is correct
4 Correct 25 ms 23808 KB Output is correct
5 Correct 22 ms 23808 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 24 ms 23808 KB Output is correct
8 Correct 21 ms 23800 KB Output is correct
9 Correct 22 ms 23800 KB Output is correct
10 Correct 21 ms 23808 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 22 ms 23936 KB Output is correct
2 Correct 23 ms 23872 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24000 KB Output is correct
2 Correct 24 ms 24184 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 24576 KB Output is correct
2 Correct 40 ms 26176 KB Output is correct
3 Correct 31 ms 24832 KB Output is correct
4 Correct 27 ms 24312 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 27104 KB Output is correct
2 Correct 53 ms 28984 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 31380 KB Output is correct
2 Correct 94 ms 38256 KB Output is correct
3 Correct 111 ms 40228 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 39488 KB Output is correct
2 Correct 183 ms 48636 KB Output is correct
3 Correct 191 ms 63320 KB Output is correct
4 Correct 241 ms 67552 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 37676 KB Output is correct
2 Correct 598 ms 92780 KB Output is correct
3 Correct 265 ms 48468 KB Output is correct
4 Correct 348 ms 71464 KB Output is correct
5 Correct 322 ms 69088 KB Output is correct
6 Correct 809 ms 67260 KB Output is correct
7 Correct 355 ms 100428 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 130276 KB Output is correct
2 Correct 335 ms 103032 KB Output is correct
3 Correct 367 ms 131072 KB Output is correct
4 Correct 316 ms 80052 KB Output is correct
5 Correct 332 ms 82500 KB Output is correct
6 Correct 333 ms 73512 KB Output is correct
7 Correct 862 ms 67960 KB Output is correct