Submission #73071

#	Time	Username	Problem	Language	Result	Execution time	Memory
73071		TuGSGeReL	Dreaming (IOI13_dreaming)	C++14	100 / 100	459 ms	9208 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){
	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(boo[v[kk][j].ff]) continue;
			boo[v[kk][j].ff]=1;
			m[v[kk][j].ff]=m[kk]+v[kk][j].ss;
			q.push(v[kk][j].ff);
		}
		q.pop();
	}
	return idx;
}
ll dia1(int k){
	bool baa[100001];
	dep[k]=0;
	memset(baa,0,sizeof baa);
	baa[k]=1;
	par[k]=-1;
	q.push(k);
	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;
			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]));
	}
	ll p=0;
	for(i=0;i<N;i++){
		if(boo[i]) continue;
		u1=dia(i);
		u2=dia1(u1);
		lc=fnd(u1,u2);
		ll s=m[u1]+m[u2]-2*m[lc],s1=0,lol=1e9,sos=0,ses=0;
		p=max(p,s);
		while(u1!=lc){
			if(abs(s1-s)<lol){
				lol=abs(s1-s);
				sos=max(s1,s);
				ses=min(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);
				ses=min(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(max(vc.back()+vc[vc.size()-2]+L,vc[vc.size()-2]+vc[vc.size()-3]+2*L),p);
	}
	else if(vc.size()==2){
		return max(vc[0]+vc[1]+L,p);
	}
	else return p;
}

Compilation message (stderr)

dreaming.cpp: In function 'long long int dia(int)':
dreaming.cpp:38:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<v[kk].size();j++){
               ~^~~~~~~~~~~~~
dreaming.cpp: In function 'long long int dia1(int)':
dreaming.cpp:62:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<v[kk].size();j++){
               ~^~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:86:47: warning: variable 'ses' set but not used [-Wunused-but-set-variable]
   ll s=m[u1]+m[u2]-2*m[lc],s1=0,lol=1e9,sos=0,ses=0;
                                               ^~~
dreaming.cpp: In function 'long long int dia(int)':
dreaming.cpp:46:9: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return idx;
         ^~~
dreaming.cpp: In function 'long long int dia1(int)':
dreaming.cpp:72:9: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return idx;
         ^~~

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