oj.uz

Submission #73049

# Submission time Handle Problem Language Result Execution time Memory
73049 2018-08-27T14:35:24 Z TuGSGeReL Dreaming (IOI13_dreaming) C++14
18 / 100
 947 ms 7928 KB 
#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 if(vc.size()==2){
		return vc[0]+vc[1]+L;
	}
	else return 0;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 7928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 7928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 7928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 7004 KB Output is correct
2 Correct 551 ms 7056 KB Output is correct
3 Correct 588 ms 7156 KB Output is correct
4 Correct 566 ms 7124 KB Output is correct
5 Correct 560 ms 7052 KB Output is correct
6 Correct 594 ms 7836 KB Output is correct
7 Correct 585 ms 7176 KB Output is correct
8 Correct 552 ms 7056 KB Output is correct
9 Correct 589 ms 7028 KB Output is correct
10 Correct 593 ms 7216 KB Output is correct
11 Correct 4 ms 2816 KB Output is correct
12 Correct 867 ms 5332 KB Output is correct
13 Correct 841 ms 5364 KB Output is correct
14 Correct 835 ms 5360 KB Output is correct
15 Correct 872 ms 5340 KB Output is correct
16 Correct 891 ms 5372 KB Output is correct
17 Correct 947 ms 4984 KB Output is correct
18 Correct 834 ms 5268 KB Output is correct
19 Correct 810 ms 5216 KB Output is correct
20 Correct 4 ms 2816 KB Output is correct
21 Correct 4 ms 2816 KB Output is correct
22 Correct 30 ms 2924 KB Output is correct
23 Correct 845 ms 5248 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 7928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 7928 KB Output isn't correct
2 Halted 0 ms 0 KB -