Submission #198566

#	Time	Username	Problem	Language	Result	Execution time	Memory
198566		Sakamotoo	Dreaming (IOI13_dreaming)	C++14	32 / 100	117 ms	25464 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define fi first
#define se second
 
const int sim=100010;
 
int p[sim];
bool udah[sim];
vector<pair<int,int> > adj[sim];
long long dp[sim];
vector<pair<long long,pair<int,int> > >sem[sim];
 
int par(int x){
	if(p[x]==x) return x;
	else return p[x]=par(p[x]);
}
 
long long cari(int x, int seb){
	for(int i=0; i<adj[x].size(); i++){
		int ind=adj[x][i].fi;
		if(ind!=seb){
			sem[x].push_back(mp(cari(ind,x)+adj[x][i].se,mp(ind,adj[x][i].se)));
		}
	}
	sort(sem[x].begin(),sem[x].end());
	reverse(sem[x].begin(),sem[x].end());
	if(sem[x].size()==0) return dp[x]=0;
	else return dp[x]=sem[x][0].fi;
}
 
long long cari2(int x,long long baw){
	if(sem[x].size()==0) return baw;
//	if(sem[x].size()>1)baw=max(baw,sem[x][1].fi);
//	long long pen=sem[x][0].fi;
	long long maxi=1e18;
	maxi=min(maxi,max(baw,dp[x]));
//	cout<<"dp "<<x<<' '<<dp[x]<<endl;
	for(int i=0; i<sem[x].size(); i++){
		long long seu=baw;
		if(i==0){
			seu=max(seu,sem[x][1].fi);
		}else {
			seu=max(seu,sem[x][0].fi);
		}
		maxi=min(maxi,cari2(sem[x][i].se.fi,seu+sem[x][i].se.se));
	}
//	cout<<x<<' '<<maxi<<endl;
	return maxi;
}
 
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    for(int i=0; i<n; i++){
    	p[i]=i;
	}
	for(int i=0; i<m; i++){
		adj[a[i]].push_back(mp(b[i],t[i]));
		adj[b[i]].push_back(mp(a[i],t[i]));
		
		int x=par(a[i]),y=par(b[i]);
		p[x]=y;
	}
	vector<int> v;
	
	for(int i=0; i<n; i++){
		int x=par(i);
		if(!udah[x]) v.push_back(x);
		udah[x]=1;	
	}
	long long has=0;
	vector<long long> jaw;
	//cout<<v.size()<<endl;
	for(int i=0; i<v.size(); i++){
	//	cout<<v[i]<<endl;
		cari(v[i],-1);
		long long baw=0;
	//	if(sem[v[i]].size()>1){
	//		baw=sem[v[i]][1].fi;
	//	}
		
		long long wk=cari2(v[i],baw);
	//	cout<<wk<<endl<<endl;
		jaw.push_back(wk);
		if(sem[v[i]].size()>1){
			has=max(has,sem[v[i]][0].fi+sem[v[i]][1].fi);
		}else if(sem[v[i]].size()==1){
			has=max(has,dp[v[i]]);
		}
	}
	sort(jaw.begin(),jaw.end());
	reverse(jaw.begin(),jaw.end());
	//long long has=jaw[0];
//	if(jaw.size()<=1){
//		for(int i=1; i<=1e9; i++){
//		}
//	}
	if(jaw.size()>=2){
		has=max(has,jaw[1]+jaw[0]+l);
//		for(int i=1; i<=1e9; i++){
//		}
	}
	if(jaw.size()>=3){
		has=max(has,jaw[1]+jaw[2]+l+l);
	}
	return has;
}

Compilation message (stderr)

dreaming.cpp: In function 'long long int cari(int, int)':
dreaming.cpp:23:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<adj[x].size(); i++){
               ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'long long int cari2(int, long long int)':
dreaming.cpp:42:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<sem[x].size(); i++){
               ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:76:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 18 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23