Submission #305625

#	Time	Username	Problem	Language	Result	Execution time	Memory
305625		youngyojun	Telegraph (JOI16_telegraph)	C++17	100 / 100	72 ms	10232 KiB

telegraph

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#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;
void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }
 
const int MAXN = 100005;
 
vector<int> G[MAXN];
 
vector<int> CV[MAXN/2];
int C[MAXN], Cn;
 
ll dp[MAXN], ds[MAXN];
 
bitset<MAXN> chk;
 
int A[MAXN], B[MAXN];
 
ll Ans;
int N;
 
void f(int i) {
	for(int v : G[i]) {
		f(v);
		ds[i] += dp[v];
	}
	for(int v : G[i]) upmax(dp[i], ll(B[v]));
	dp[i] += ds[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 k = -1;
 
		for(int j = i;;) {
			chk[j] = true;
			V.pb(j);
			j = A[j];
			if(chk[j]) {
				k = j;
				break;
			}
		}
 
		int ki = -1;
		for(int j = 0; j < sz(V); j++)
			if(V[j] == k) ki = j;
 
		if(ki < 0 || V.empty()) continue;
 
		Cn++;
		for(int j = ki; j < sz(V); j++) {
			C[V[j]] = Cn;
			CV[Cn].pb(V[j]);
		}
	}
 
	if(1 == Cn && sz(CV[1]) == N) {
		puts("0");
		return 0;
	}
 
	for(int i = 1; i <= N; i++) {
		if(C[i] && C[A[i]]) continue;
		G[A[i]].pb(i);
	}
 
	for(int i = 1; i <= N; i++) if(C[i]) f(i);
 
	for(int i = 1; i <= Cn; i++) {
		vector<int> &V = CV[i];
		const int n = sz(V);
 
		ll ret = 0;
		bool flag = false;
 
		for(int j = 0; j < n; j++) {
			ll a = dp[V[j]], b = ds[V[j]] + B[V[(j-1+n)%n]];
			if(a >= b) {
				ret += a;
				flag = true;
			} else {
				ret += b;
			}
		}
 
		if(flag) {
			Ans += ret;
			continue;
		}
 
		ll sum = ret; ret = 0;
		for(int j = 0; j < n; j++)
			upmax(ret, sum - ds[V[j]] - B[V[(j-1+n)%n]] + dp[V[j]]);
		Ans += ret;
	}
 
	for(int i = 1; i <= N; i++) Ans -= B[i];
 
	cout << (-Ans) << endl;
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30