답안 #386391

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
386391 2021-04-06T13:53:04 Z kshitij_sodani Islands (IOI08_islands) C++14
0 / 100
2000 ms 131076 KB
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'


llo n;
vector<pair<llo,llo>> adj[1000001];
vector<pair<llo,llo>> adj2[1000001];

llo par[1000001];
llo find(llo no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
llo dp[1000001][2];
pair<llo,llo> cur;
vector<pair<llo,llo>> pp;
vector<pair<llo,llo>> xx;


vector<llo> tt;
void dfs(llo no,llo par2=-1){
	
	if(no==cur.b){
		pp=xx;
	}
	tt.pb(no);
	for(auto j:adj[no]){
		/*if(j.a==cur.a and no==cur.b){
			continue;
		}
		if(j.a==cur.b and no==cur.a){
			continue;
		}*/
		if(j.a!=par2){
			xx.pb({j.a,j.b});
			dfs(j.a,no);
			xx.pop_back();
		}
	}
}
llo vis[1000001];
llo maa=0;

void dfs2(llo no,llo par2=-1){
	dp[no][0]=0;
	dp[no][1]=0;
	vector<llo> ss;
	llo su=0;

	for(auto j:adj2[no]){
		if(j.a!=par2){
			dfs2(j.a,no);
	//		dp[no][0]=max(dp[no][0],j.b+dp[j.a][0]);
			su+=dp[j.a][1];
			ss.pb(dp[j.a][0]+j.b);
		}
	}
	sort(ss.begin(),ss.end());
	reverse(ss.begin(),ss.end());
	dp[no][1]=0;
	dp[no][0]=0;
	for(llo i=0;i<ss.size();i++){
		if(i==2){
			break;
		}
		if(i==0){
			if(ss[i]>=0){
				dp[no][0]+=ss[i];
			}
		}
		if(ss[i]>=0){
			dp[no][1]+=ss[i];
		}
	}
	dp[no][1]=max(dp[no][1],dp[no][0]);
	maa=max(maa,dp[no][1]);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n;i++){
		par[i]=i;
	}
	vector<pair<pair<llo,llo>,llo>> ed;
	for(llo i=0;i<n;i++){
		llo aa,cc;
		cin>>aa>>cc;
		aa--;
		llo x=find(i);
		llo y=find(aa);
		if(x!=y){
			par[x]=y;
			adj[i].pb({aa,cc});
			adj[aa].pb({i,cc});
		}
		else{
			ed.pb({{i,aa},cc});
			//cout<<i<<":"<<aa<<":"<<cc<<endl;
		}
		
	}
	llo ans=0;
	for(auto j:ed){
		cur=j.a;
		llo cost=0;
		tt.clear();
		dfs(j.a.a);
		pp.pb({cur.a,j.b});
		for(auto i:pp){
			vis[i.a]=1;
		}
		vector<pair<pair<llo,llo>,llo>> pc;
		pc.pb(j);

		for(auto i:tt){
			for(auto k:adj[i]){
				if(vis[k.a]+vis[i]<2){
					//adj2[i].pb(k);
				}
				else{
					if(k.a<i){
						pc.pb({{i,k.a},k.b});
					}
				}
			}
		}
	/*	for(auto i:pc){
			cout<<i.a.a<<","<<i.a.b<<","<<i.b<<endl;
		}*/
		if(pp.size()==2){
			llo zz5=0;
			for(auto i:tt){
				for(auto k:adj[i]){
					//cout<<i<<":"<<k.a<<":"<<k.b<<endl;
					if(vis[k.a]+vis[i]<2){
						adj2[i].pb(k);
					}
					else{
						//if(k.a<i){
						zz5=max(zz5,k.b);

						//}
					}
				}
			}
			maa=0;
			for(auto i:pp){
				dfs2(i.a);
			}

			zz5=max(zz5,j.b);
			cost=max(cost,maa);
			//cost=max(cost,dp[pp[0].a][1]+dp[pp[1].a][1]);
			cost=max(cost,dp[pp[0].a][0]+dp[pp[1].a][0]+zz5);
			ans+=cost;
			while(true){
				continue;
			}
			//cout<<cost<<":"<<endl;
			continue;
		}
		maa=0;
		for(auto i:tt){
				for(auto k:adj[i]){
					if(vis[k.a]+vis[i]<2){
						adj2[i].pb(k);
					}
					else{

					}
				}
			}
		for(auto i:pp){
			dfs2(i.a);
		}
		cost=max(cost,maa);
		vector<pair<llo,llo>> pp2=pp;
		for(auto i:pp){
			pp2.pb(i);
		}
		llo xx=pp.size();
		multiset<llo> zz;
		vector<llo> xd;
		llo su2=0;
		/*for(auto i:pp2){
			cout<<i.a<<"<"<<i.b<<endl;
		}*/
		for(llo i=0;i<pp2.size();i++){
			if(i>=xx){
				auto jj=zz.find(xd[i-xx]);
				zz.erase(jj);
			}
			su2+=pp2[i].b;
			if(xd.size()){
				auto jj=xd.end();
				jj--;
				cost=max(cost,dp[pp2[i].a][0]+su2+(*jj));
			}
			xd.pb(dp[pp2[i].a][0]-su2);
			zz.insert(xd.back());
		}
		ans+=cost;








	}
	cout<<ans<<endl;





 
 
	return 0;
}
 

Compilation message

islands.cpp: In function 'void dfs2(llo, llo)':
islands.cpp:72:15: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(llo i=0;i<ss.size();i++){
      |              ~^~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:199:16: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |   for(llo i=0;i<pp2.size();i++){
      |               ~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2092 ms 47340 KB Time limit exceeded
2 Execution timed out 2073 ms 47340 KB Time limit exceeded
3 Incorrect 30 ms 47468 KB Output isn't correct
4 Execution timed out 2076 ms 47340 KB Time limit exceeded
5 Incorrect 32 ms 47340 KB Output isn't correct
6 Execution timed out 2079 ms 47340 KB Time limit exceeded
7 Execution timed out 2077 ms 47340 KB Time limit exceeded
8 Incorrect 31 ms 47340 KB Output isn't correct
9 Execution timed out 2076 ms 47340 KB Time limit exceeded
10 Execution timed out 2085 ms 47340 KB Time limit exceeded
11 Execution timed out 2088 ms 47340 KB Time limit exceeded
# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 47744 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2082 ms 47468 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 49644 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 95 ms 58784 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 165 ms 79708 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 267 ms 94928 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 381 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 383 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -