oj.uz

Submission #53694

# Submission time Handle Problem Language Result Execution time Memory
53694 2018-07-01T04:53:14 Z 윤교준(#1438) Islands (IOI08_islands) C++11
44 / 100
 2000 ms 175832 KB 
#include <bits/stdc++.h>
#define pb push_back
#define sz(V) ((int)(V).size())
#define rb(x) ((x)&(-(x)))
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;

const int MAXN = 1000005;

vector<int> G[MAXN];

vector<vector<int>> CY;
vector<vector<ll>> SCY;

ll dep[MAXN], mxdep[MAXN];

int CI[MAXN];
int A[MAXN], B[MAXN];
bitset<MAXN> chk;
bitset<MAXN> isCV;

ll Ans;
int N;

int dfs1(vector<int> &V, int i) {
	chk[i] = true;
	V.pb(i);
	int v = A[i];
	if(chk[v]) return v;
	return dfs1(V, v);
}
void dfs2(int i) {
	mxdep[i] = dep[i];
	for(int v : G[i]) {
		dep[v] = dep[i] + B[v];
		dfs2(v);
		upmax(mxdep[i], mxdep[v]);
	}
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i <= N; i++) cin >> A[i] >> B[i];

	for(int i = 1; i <= N; i++) if(!chk[i]) {
		vector<int> V;
		int t = dfs1(V, i);

		CY.pb(vector<int>());
		int j = 0;

		for(; j < sz(V) && V[j] != t; j++);
		for(; j < sz(V); j++) CY.back().pb(V[j]);
		if(CY.back().empty()) CY.pop_back();
	}

	for(int i = 0; i < sz(CY); i++) {
		for(int v : CY[i]) {
			isCV[v] = true;
			CI[v] = i;
		}
	}

	for(int i = 1; i <= N; i++) {
		if(isCV[i] && isCV[A[i]]) continue;
		G[A[i]].pb(i);
	}
	for(int i = 1; i <= N; i++) if(isCV[i])
		dfs2(i);
	
	for(int i = 0; i < sz(CY); i++) {
		SCY.pb(vector<ll>(1, 0));
		for(int v : CY[i])
			SCY[i].pb(SCY[i].back() + B[v]);
	}

	for(int i = 0; i < sz(CY); i++) {
		ll ret = 0;
		for(int ai = 0; ai < sz(CY[i]); ai++) {
			for(int bi = ai+1; bi < sz(CY[i]); bi++) {
				ll t = mxdep[CY[i][ai]] + mxdep[CY[i][bi]];
				ll l = SCY[i][bi] - SCY[i][ai];
				t += max(l, SCY[i].back() - l);

				upmax(ret, t);
			}
		}
		Ans += ret;
	}

	cout << Ans << endl;
	return 0;
}

Subtask #1
27.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23800 KB Output is correct
2 Incorrect 23 ms 24044 KB Output isn't correct
3 Correct 23 ms 24224 KB Output is correct
4 Correct 22 ms 24224 KB Output is correct
5 Correct 23 ms 24224 KB Output is correct
6 Correct 22 ms 24224 KB Output is correct
7 Correct 25 ms 24224 KB Output is correct
8 Correct 22 ms 24224 KB Output is correct
9 Correct 22 ms 24224 KB Output is correct
10 Incorrect 22 ms 24224 KB Output isn't correct
11 Correct 22 ms 24224 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24388 KB Output is correct
2 Correct 28 ms 24560 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 25256 KB Output is correct
2 Correct 432 ms 27260 KB Output is correct
3 Correct 35 ms 27260 KB Output is correct
4 Incorrect 32 ms 27260 KB Output isn't correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 29292 KB Output is correct
2 Correct 649 ms 32344 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 751 ms 39848 KB Output is correct
2 Execution timed out 2080 ms 44108 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1820 ms 56124 KB Output is correct
2 Execution timed out 2071 ms 74804 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 175832 KB Output is correct
2 Incorrect 469 ms 175832 KB Output isn't correct
3 Halted 0 ms 0 KB -