oj.uz

Submission #101053

# Submission time Handle Problem Language Result Execution time Memory
101053 2019-03-16T07:49:12 Z maruii Islands (IOI08_islands) C++14
21 / 100
 1367 ms 132096 KB 
#include <bits/stdc++.h>
using namespace std;
bool vis[1000001];
vector<pair<int, int> > edge[1000001];
long long dp1[1000001], dp2[1000001];
vector<int> vec;
void dfs(int x){
	vec.push_back(x);
	vis[x] = 1;
	dp1[x] = dp2[x] = 0;
	long long mx1 = 0, mx2 = 0;
	for(auto i: edge[x]){
		if(vis[i.second]) continue; 
		dfs(i.second);
		dp1[x] = max(dp1[x], dp1[i.second]);
		long long t = dp2[i.second]+i.first;
		dp2[x] = max(dp2[x], t);
		if(mx1 <= t) mx2 = mx1, mx1 = t;
		else if(mx2 < t) mx2 = t;
	}
	dp1[x] = max(dp1[x], mx1+mx2);
}
long long getD(int x){
	dfs(x);
	return dp1[x];
}
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N; cin>>N;
	for(int i=1; i<=N; ++i){
		int a,b; cin>>a>>b;
		edge[i].push_back({b, a});
		edge[a].push_back({b, i});
	}
	long long ans = 0;
	for(int i=1; i<=N; ++i){
		if(vis[i]) continue;
		long long t = getD(i);
		for(auto j: vec) reverse(edge[j].begin(), edge[j].end()), vis[j] = 0;
		vec.clear();
		t = max(t, getD(i));
		vec.clear();
		ans += t;

	}
	cout<<ans;
	return 0;
}

Subtask #1
21.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23808 KB Output is correct
2 Correct 28 ms 23800 KB Output is correct
3 Incorrect 27 ms 23936 KB Output isn't correct
4 Correct 25 ms 23936 KB Output is correct
5 Correct 26 ms 23936 KB Output is correct
6 Correct 24 ms 23808 KB Output is correct
7 Incorrect 24 ms 23800 KB Output isn't correct
8 Incorrect 26 ms 23808 KB Output isn't correct
9 Incorrect 28 ms 23848 KB Output isn't correct
10 Correct 27 ms 23928 KB Output is correct
11 Correct 31 ms 23820 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 23928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 23936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 25040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 29148 KB Output is correct
2 Incorrect 80 ms 31988 KB Output isn't correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 39908 KB Output is correct
2 Correct 148 ms 43716 KB Output is correct
3 Incorrect 193 ms 53924 KB Output isn't correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 230 ms 51520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 103332 KB Output is correct
2 Runtime error 1367 ms 132096 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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