제출 #335483

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
335483		keta_tsimakuridze	Islands (IOI08_islands)	C++14	27 / 100	856 ms	131072 KiB

islands

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=1e6+5;
long long mx,h,ans1,dm[N],n,m,a[N],b[N],fix[N],sz,mx1,c,k,u,ans,v;
vector<pair<int,long long> >V[N],cycle;
void dfs(int u,int p,long long h){
	if(h>mx) {
		mx=h; c=u;
	}
	for(int i=0;i<V[u].size();i++){
		if(fix[V[u][i].f]!=2 && V[u][i].f!=p){
			dfs(V[u][i].f,u,h+V[u][i].s);
		}
	}
}
void diameter(int u){
    mx=0;
	dfs(u,0,0);dm[u]=mx;
	dfs(c,0,0);
	ans1=max(ans1,mx);	
}
int main(){
	cin>>n;
	for(k=1;k<=n;k++){
		cin>>a[k]>>b[k];
		V[a[k]].push_back({k,b[k]});
	}
	for(k=1;k<=n;k++){
		if(!fix[k]){
			u=k;
			ans1=0; sz=0; cycle.clear();
			while(!fix[u]){
				fix[u]=1;
				u=a[u];
			}
			while(fix[u]!=2){
				fix[u]=2;
				u=a[u];
				cycle.push_back({u,b[u]});
				sz+=b[u];
			}
			for(int i=0;i<cycle.size();i++){
				diameter(cycle[i].f);
			} 
			mx=mx1=dm[cycle[0].f]; ans1=max(ans1,sz-cycle[0].s);
			long long bef=cycle[0].s;
			for(int i=1;i<cycle.size();i++){
			
				ans1=max(ans1,bef+mx+dm[cycle[i].f]);
				ans1=max(ans1,sz+mx1-bef+dm[cycle[i].f]);
				mx=max(mx,dm[cycle[i].f]-bef);
				mx1=max(mx1,dm[cycle[i].f]+bef);
				bef+=cycle[i].s;
			}
			ans+=ans1;
		} 
	}
	cout<<ans;
}

컴파일 시 표준 에러 (stderr) 메시지

islands.cpp: In function 'void dfs(int, int, long long int)':
islands.cpp:12:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:44:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |    for(int i=0;i<cycle.size();i++){
      |                ~^~~~~~~~~~~~~
islands.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |    for(int i=1;i<cycle.size();i++){
      |                ~^~~~~~~~~~~~~

• Subtask 1: 24 / 33
• Subtask 2: 3 / 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