Submission #1170790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170790		Dan4Life	Islands (IOI08_islands)	C++20	100 / 100	809 ms	96924 KiB

islands

#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 ar3 = array<int,3>;
using vi = vector<int>;
const int mxN = (int)1e6+2;

vi w;
ll n, far, SS;
bitset<mxN> cyc;
int adj[3][mxN*2];
int adjH[mxN]; int8_t vis[mxN];
int allowed_S; bool curCnt = 0;
vi xd;

pair<ll,int> dfs2(int s) {
    struct F { int s, x, bn; ll b, w; };
    vector<F> st;
    st.push_back({s, adjH[s], s, 0, 0});
    vis[s]++;
    while (!st.empty()) {
        auto &f = st.back();
        if (f.x) {
            int e = f.x; 
            f.x = adj[1][e];
            int u = adj[0][e]; 
            ll w = adj[2][e];
            if (vis[u] != curCnt) continue;
            vis[u]++;
            st.push_back({u, adjH[u], u, 0, w});
        } else {
            F t = st.back(); st.pop_back();
            if (!st.empty()) {
                ll cand = t.b + t.w;
                if (cand > st.back().b) { 
                    st.back().b = cand; 
                    st.back().bn = t.bn;
                }
            } else return {t.b, t.bn};
        }
    }
    return {0,0};
}

ll dfs(int s, int p) {
    struct F { int s, x, par; ll b, w; };
    vector<F> st;
    st.push_back({s, adjH[s], p, 0, 0});
    while (!st.empty()) {
        auto &f = st.back();
        if (f.x) {
            int e = f.x; 
            f.x = adj[1][e];
            int u = adj[0][e]; 
            ll w = adj[2][e];
            if (u == f.par || cyc[u]) continue;
            st.push_back({u, adjH[u], f.s, 0, w});
        } else {
            auto t = st.back(); st.pop_back();
            if (!st.empty()) {
                ll cand = t.b + t.w;
                if (cand > st.back().b)
                    st.back().b = cand;
            } else return t.b;
        }
    }
    return 0;
}


ll compute_diam(int s){
	allowed_S = s; curCnt = 0;
	int a = dfs2(s).second; curCnt=1;
	return dfs2(a).first;
}

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;
		adj[0][i*2-1]=i, adj[1][i*2-1]=adjH[x],adj[2][i*2-1]=w; adjH[x]=i*2-1;
		adj[0][i*2]=x, adj[1][i*2]=adjH[i],adj[2][i*2]=w; adjH[i]=i*2;
	}
	for(int i = 1; i <= n; i++){ 
		if(vis[i]) continue;
		int x = i; vi v; v.clear(); v.shrink_to_fit();
		ll sum = 0, totP=0;
		while(!vis[x]) vis[x]=1,v.pb(x),x=adj[0][x*2];
		for(auto u : v) vis[u]=0; v.clear(); v.shrink_to_fit();
		while(!cyc[x]) cyc[x]=1,v.pb(x),x=adj[0][x*2];
		for(auto u : v) sum = max(sum, compute_diam(u));
		int m = sz(v); multiset<ll> S; S.clear();
		for(int i = 0; i < m; i++){
			ll dis = dfs(v[i],0);
			sum=max(sum,dis); S.insert(dis-totP);	
			totP+=(ll)adj[2][v[i]*2];
		}
		ll ss = 0;
		for(int i = 0; i < m; i++){
			ll dis = dfs(v[i],0); 
			S.erase(S.find(dis-ss));
			if(sz(S)) sum=max(sum, dis+totP+ss+*prev(end(S))); 
			S.insert(dis-(totP+ss)); ss+=(ll)adj[2][v[i]*2];
		}
		ans+=sum;
	}
	cout << ans << "\n";
}

• Subtask 1: 33 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10