oj.uz

Submission #53702

# Submission time Handle Problem Language Result Execution time Memory
53702 2018-07-01T05:01:00 Z 윤교준(#1438) Islands (IOI08_islands) C++11
60 / 100
 2000 ms 196312 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<int> VT[MAXN];

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

ll dep[MAXN], mxdep[MAXN], mxtl[MAXN];
ll dst[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(vector<int> &V, int i) {
	V.pb(i); mxdep[i] = dep[i];
	for(int v : G[i]) {
		dep[v] = dep[i] + B[v];
		dfs2(V, v);
		upmax(mxdep[i], mxdep[v]);
	}
}
void dfs3(int i) {
	for(int v : G[i]) if(!dst[v]) {
		dst[v] = dst[i] + B[v];
		dfs3(v);
	}
	if(!isCV[i] && !dst[A[i]]) {
		dst[A[i]] = dst[i] + B[i];
		dfs3(A[i]);
	}
}

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(VT[i], i);

		dst[i] = 1;
		dfs3(i);

		int hi = -1; ll hd = 0;
		for(int v : VT[i]) if(hd < dst[v]) {
			hi = v; hd = dst[v];
		}

		for(int v : VT[i]) dst[v] = 0;
		dst[hi] = 1;
		dfs3(hi);

		hd = 0;
		for(int v : VT[i]) upmax(hd, dst[v]);

		mxtl[i] = hd - 1;
	}
	
	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);
			}
		}
		for(int v : CY[i]) upmax(ret, mxtl[v]);
		Ans += ret;
	}

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

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 47300 KB Output is correct
2 Correct 48 ms 47468 KB Output is correct
3 Correct 49 ms 47548 KB Output is correct
4 Correct 44 ms 47600 KB Output is correct
5 Correct 43 ms 47652 KB Output is correct
6 Correct 48 ms 47700 KB Output is correct
7 Correct 44 ms 47700 KB Output is correct
8 Correct 42 ms 47700 KB Output is correct
9 Correct 43 ms 47700 KB Output is correct
10 Correct 49 ms 47700 KB Output is correct
11 Correct 42 ms 47700 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 47740 KB Output is correct
2 Correct 43 ms 47740 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 47868 KB Output is correct
2 Correct 55 ms 47936 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 48892 KB Output is correct
2 Correct 456 ms 51000 KB Output is correct
3 Correct 57 ms 51000 KB Output is correct
4 Correct 54 ms 51000 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 52348 KB Output is correct
2 Correct 645 ms 56272 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 822 ms 62260 KB Output is correct
2 Execution timed out 2041 ms 67932 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1638 ms 78972 KB Output is correct
2 Execution timed out 2058 ms 93428 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 93428 KB Output is correct
2 Execution timed out 2074 ms 145984 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 688 ms 196312 KB Output is correct
2 Correct 602 ms 196312 KB Output is correct
3 Execution timed out 2075 ms 196312 KB Time limit exceeded
4 Halted 0 ms 0 KB -