Submission #1102215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102215		_rain_	Islands (IOI08_islands)	C++14	27 / 100	837 ms	131072 KiB

islands

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
#define fi first 
#define se second

const int N = 1000000;
vector<ii> adj[N+2];
int en[N+2],l[N+2],id[N+2],times=0,n,root;
vector<int> s;
bool vis[N+2];
ll mxw,d[N+2];
void add_edge(int u , int v , int l){
	adj[u].push_back({v,l});
	adj[v].push_back({u,l});
	return;
}
void search(int u){
	s.push_back(u);
	id[u]=times;
	for (auto& x : adj[u]){
		int to=x.first , w=x.second;
		if (id[to]!=0) continue;
		search(to);
	}
	return;
}
void dfs(int u , int p){
	vis[u] = true;
	if (mxw <= d[u]){
		root=u;
		mxw=d[u];
	}
	for (auto& x : adj[u]){
		int to=x.first , w=x.second;
		if (vis[to]) continue;
		d[to]=d[u]+w;
		dfs(to,u);
	}
	return;
}
void Find(int root){
	mxw = 0;
	for (auto& u:s) {
		d[u]=vis[u]=0;
	}
	dfs(root,root);
}



int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i){
		cin >> en[i] >> l[i];
		add_edge(i,en[i],l[i]);
	}
	for (int i = 1; i <= n; ++i) {
		sort(adj[i].begin(),adj[i].end(),
		[=](ii x , ii y){
				if (x.se!=y.se) return x.se>y.se;
		});
	}
	ll ans=0;
	for (int i = 1; i <= n; ++i){
		if (!id[i]){
			++times,s.clear();
			search(i);
			root = i;
			Find(root);
			Find(root);
			ans+=mxw;
		}
	}
	cout << ans;
}

Compilation message (stderr)

islands.cpp: In function 'void search(int)':
islands.cpp:24:20: warning: unused variable 'w' [-Wunused-variable]
   24 |   int to=x.first , w=x.second;
      |                    ^
islands.cpp: In lambda function:
islands.cpp:66:3: warning: control reaches end of non-void function [-Wreturn-type]
   66 |   });
      |   ^

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