oj.uz

Submission #53706

# Submission time Handle Problem Language Result Execution time Memory
53706 2018-07-01T05:14:59 Z 윤교준(#1438) Islands (IOI08_islands) C++11
100 / 100
 1659 ms 262144 KB 
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_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;
typedef pair<ll, int> pli;

const int MAXN = 1000005;

vector<int> G[MAXN];

vector<int> VT[MAXN];

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

ll mt[MAXN];

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 ci = 0; ci < sz(CY); ci++) {
		ll ret = 0, L = SCY[ci].back();
		int n = sz(CY[ci]);

		for(int i = 0; i < n; i++)
			mt[i] = mxdep[CY[ci][i]] + SCY[ci][i];
		for(int i = n-2; 0 <= i; i--) upmax(mt[i], mt[i+1]);

		deque<pli> PQ;

		for(int i = 0, j = 0; i < n; i++) {
			for(; !PQ.empty() && PQ[0].second <= i; PQ.pop_front());
			for(j = max(i+1, j); j < n && SCY[ci][j] < (L+1)/2 + SCY[ci][i]; j++) {
				ll t = mxdep[CY[ci][j]] - SCY[ci][j];
				for(; !PQ.empty() && PQ.back().first <= t; PQ.pop_back());
				PQ.eb(t, j);
			}
			if(j < n) upmax(ret, mt[j] + mxdep[CY[ci][i]] - SCY[ci][i]);
			if(!PQ.empty()) upmax(ret, PQ[0].first + mxdep[CY[ci][i]] + SCY[ci][i] + L);
		}

		for(int v : CY[ci]) 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 53 ms 47352 KB Output is correct
2 Correct 46 ms 47544 KB Output is correct
3 Correct 50 ms 47664 KB Output is correct
4 Correct 50 ms 47664 KB Output is correct
5 Correct 47 ms 47664 KB Output is correct
6 Correct 42 ms 47664 KB Output is correct
7 Correct 49 ms 47664 KB Output is correct
8 Correct 44 ms 47664 KB Output is correct
9 Correct 46 ms 47664 KB Output is correct
10 Correct 47 ms 47692 KB Output is correct
11 Correct 44 ms 47692 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47692 KB Output is correct
2 Correct 51 ms 47804 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 47804 KB Output is correct
2 Correct 52 ms 47988 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 48876 KB Output is correct
2 Correct 70 ms 51132 KB Output is correct
3 Correct 60 ms 51132 KB Output is correct
4 Correct 50 ms 51132 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 52408 KB Output is correct
2 Correct 87 ms 56376 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 62360 KB Output is correct
2 Correct 164 ms 68324 KB Output is correct
3 Correct 187 ms 79140 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 82888 KB Output is correct
2 Correct 318 ms 97540 KB Output is correct
3 Correct 301 ms 115184 KB Output is correct
4 Correct 421 ms 137180 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 137180 KB Output is correct
2 Correct 925 ms 154200 KB Output is correct
3 Correct 419 ms 154200 KB Output is correct
4 Correct 528 ms 178628 KB Output is correct
5 Correct 616 ms 190872 KB Output is correct
6 Correct 1625 ms 190872 KB Output is correct
7 Correct 550 ms 241680 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 632 ms 262144 KB Output is correct
2 Correct 640 ms 262144 KB Output is correct
3 Correct 538 ms 262144 KB Output is correct
4 Correct 780 ms 262144 KB Output is correct
5 Correct 526 ms 262144 KB Output is correct
6 Correct 555 ms 262144 KB Output is correct
7 Correct 1659 ms 262144 KB Output is correct