Submission #73045

#	Time	Username	Problem	Language	Result	Execution time	Memory
73045		TuGSGeReL	Dreaming (IOI13_dreaming)	C++14	0 / 100	861 ms	7932 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>

#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back
#define ss second
#define ff first
#define ext exit(0)
using namespace std;
int i,m[100001],par[100001],dep[100001],u1,u2,lc;
vector<pair<int,int> >v[100001];
bool boo[100001];
queue<ll>q;
vector<ll> vc;
ll fnd(int v1,int v2){
	if(dep[v1]<dep[v2]) swap(v1,v2);
	while(dep[v1]>dep[v2]){
		v1=par[v1];
	}
	if(v1==v2) return v1;
	while(v1!=v2){
		v1=par[v1];
		v2=par[v2];
	}
	return v1;
}
ll dia(int k){
	bool baa[100001];
	dep[k]=0;
	memset(baa,0,sizeof baa);
	baa[k]=1;
	par[k]=-1;
	q.push(k);
	boo[k]=1;
	ll idx,s=0;
	while(!q.empty()){
		int kk=q.front();
		if(m[kk]>=s){
			s=m[kk];
			idx=kk;
		}
		for(int j=0;j<v[kk].size();j++){
			if(baa[v[kk][j].ff]) continue;
			boo[v[kk][j].ff]=1;
			baa[v[kk][j].ff]=1;
			m[v[kk][j].ff]=m[kk]+v[kk][j].ss;
			par[v[kk][j].ff]=kk;
			dep[v[kk][j].ff]=dep[kk]+1;
			q.push(v[kk][j].ff);
		}
		q.pop();
	}
	return idx;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for(i=0;i<M;i++){
		v[A[i]].pub(mp(B[i],T[i]));
		v[B[i]].pub(mp(A[i],T[i]));
	}
	for(i=0;i<N;i++){
		if(boo[i]) continue;
		u1=dia(i);
		u2=dia(u1);
		lc=fnd(u1,u2);
			ll s=m[u1]+m[u2]-2*m[lc],s1=0,lol=1e9,sos=0;
		while(u1!=lc){
			if(abs(s1-s)<lol){
				lol=abs(s1-s);
				sos=max(s1,s);
			}
			s1+=m[u1]-m[par[u1]];
			s-=m[u1]-m[par[u1]];
			u1=par[u1];
		}
		s=m[u1]+m[u2]-2*m[lc],s1=0,lol=1e9;
		while(u2!=lc){
			if(abs(s1-s)<lol){
				lol=abs(s1-s);
				sos=max(s1,s);
			}
			s1+=m[u2]-m[par[u2]];
			s-=m[u2]-m[par[u2]];
			u2=par[u2];
		}
		vc.pub(sos);
	}
	sort(vc.begin(),vc.end());
	if(vc.size()>=3){
		return max(vc.back()+vc[vc.size()-2]+L,vc[vc.size()-2]+vc[vc.size()-3]+2*L);
	}
	else {
		return vc.back()+vc[vc.size()-2]+L;
	}
}

Compilation message (stderr)

dreaming.cpp: In function 'long long int dia(int)':
dreaming.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<v[kk].size();j++){
               ~^~~~~~~~~~~~~
dreaming.cpp:55:9: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return idx;
         ^~~

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