제출 #1162582

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162582		Dan4Life	Linear Garden (IOI08_linear_garden)	C++20	0 / 100	83 ms	131072 KiB

linear_garden

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
using ll = long long;
using ar2 = array<int,2>;
using vi = vector<int>;
const int mxN = (int)1e6+10;

vi w;
ar2 nx[mxN];
ll n, far, SS;
bitset<mxN> cyc;
vector<ar2> adj[mxN];
ll vis[mxN], pref[mxN];

void dfs(int s, int p){
	far=max(far,vis[s]); w.pb(s);
	for(auto [u,w] : adj[s]){
		if(vis[u] or (cyc[u] and SS!=u)) continue;
		vis[u] = vis[s]+w; dfs(u,s);
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n; ll ans = 0;
	for(int i = 1; i <= n; i++){
		int x, w; cin >> x >> w; nx[i]={x,w}; 
		adj[x].pb({i,w}); adj[i].pb({x,w});
	}
	for(int i = 1; i <= n; i++){
		if(vis[i]) continue;
		int x = i; vi v; v.clear();
		
		while(!vis[x]){
			vis[x]=1,v.pb(x),x=nx[x][0];
		}
		
		for(auto u : v) vis[u]=0; 
		v.clear();
		
		while(!cyc[x]){
			cyc[x]=1,v.pb(x),x=nx[x][0];
		}
		
		ll sum = 0; pref[0] = 0;
		for(auto u : v){ 
			far = 0; w.clear(); dfs(u,0); int a; 
			for(auto xx : w) if(vis[xx]==far) a=xx;
			ll xd = far; SS = u;
			for(auto xx : w) vis[xx]=0;
			w.clear(); dfs(a,0); vis[u] = xd;
			sum = max(sum, far);
		}
		multiset<ll> S; S.clear(); int m = sz(v); 
		for(int i = 0; i < m; i++) v.pb(v[i]);
		for(int i = 0; i < sz(v); i++){
			sum=max(sum,vis[v[i]]);
			pref[i+1]=pref[i]+(ll)nx[v[i]][1];
			if(i<m) S.insert(vis[v[i]]-pref[i]);	
		}
		for(int i = m; i < sz(v); i++){
			S.erase(S.find(vis[v[i-m]]-pref[i-m]));
			sum=max(sum, vis[v[i]]+pref[i]+*prev(end(S))); 
			S.insert(vis[v[i]]-pref[i]);
		}
		ans+=sum; for(auto u : v) vis[u]=1;
	}
	cout << ans << "\n";
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 4
• Subtask 7: 0 / 4
• Subtask 8: 0 / 4
• Subtask 9: 0 / 4
• Subtask 10: 0 / 4
• Subtask 11: 0 / 4
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5