oj.uz

Submission #101068

# Submission time Handle Problem Language Result Execution time Memory
101068 2019-03-16T08:57:59 Z maruii Islands (IOI08_islands) C++14
9 / 100
 721 ms 132096 KB 
#include <bits/stdc++.h>
using namespace std;
bool vis[1000001], isC[1000001];
vector<pair<int, int> > edge[1000001];
long long dp1[1000001], dp2[1000001], D;
int prt[1000001], pdg[1000001], dth[1000001], X, C;
vector<int> vec;
void dfs(int x, int p, int pp){
	vis[x] = 1;
	dp1[x] = dp2[x] = 0;
	long long mx1 = 0, mx2 = 0, m2 = 0;
	bool flag = 1;
	for(auto i: edge[x]){
		if(i.second == p && i.first == pp && flag){
			flag = 0;
			continue;
		}
		if(vis[i.second]){
			if(dth[i.second] > dth[x]) continue;
			vec.clear();
			for(int v=x; v!=i.second; v=prt[v]) vec.push_back(v), isC[v] = 1;
			isC[i.second] = 1;
			X = i.first;
			C = i.second;
			continue;
		}
		prt[i.second] = x;
		pdg[i.second] = i.first;
		dth[i.second] = dth[x] + 1;
		dfs(i.second, x, i.first);
		if(x==C && !isC[i.second]) m2 = max(m2, dp2[i.second]+i.first);
		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;
	}
	if(x==C){
		long long t = X;
		vector<long long> v1;
		for(auto i: vec){
			if(v1.size() && v1.back() > t+dp2[i]) v1.push_back(v1.back());
			else v1.push_back(t+dp2[i]);
			dp2[x] = max(dp2[x], t+dp2[i]);
			t += pdg[i];
		}
		reverse(vec.begin(), vec.end());
		t = 0;
		int cnt = vec.size()-2;
		long long s = 0;
		for(auto i: vec){
			if(cnt<0) break;
			t += pdg[i];
			for(auto j: edge[i]){
				if(isC[j.second]) continue;
				s = max(s, dp2[j.second]+t);
			}
			s = max(s, t+dp2[i]);
			dp1[x] = max(dp1[x], s+v1[cnt]);
			--cnt;
		}
		dp1[x] = max(dp1[x], v1.back()+m2);
	}
	dp1[x] = max(dp1[x], mx1+mx2);
}
long long getD(int x){
	dfs(x, 0, 0);
	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;
		ans += getD(i);
	}
	cout<<ans;
	return 0;
}

Subtask #1
9.0 / 33.0

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

Subtask #2
0 / 3.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 93064 KB Output is correct
2 Runtime error 721 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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