oj.uz

Submission #73045

# Submission time Handle Problem Language Result Execution time Memory
73045 2018-08-27T14:30:32 Z TuGSGeReL Dreaming (IOI13_dreaming) C++14
0 / 100
 861 ms 7932 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 {
		return vc.back()+vc[vc.size()-2]+L;
	}
}

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 60 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 60 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 60 ms 7928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 7036 KB Output is correct
2 Correct 820 ms 7012 KB Output is correct
3 Correct 571 ms 7000 KB Output is correct
4 Correct 569 ms 7036 KB Output is correct
5 Correct 581 ms 7032 KB Output is correct
6 Correct 598 ms 7932 KB Output is correct
7 Correct 603 ms 7284 KB Output is correct
8 Correct 546 ms 7164 KB Output is correct
9 Correct 561 ms 6920 KB Output is correct
10 Correct 592 ms 7280 KB Output is correct
11 Correct 5 ms 2816 KB Output is correct
12 Correct 855 ms 5248 KB Output is correct
13 Correct 849 ms 5272 KB Output is correct
14 Correct 861 ms 5296 KB Output is correct
15 Correct 853 ms 5340 KB Output is correct
16 Correct 835 ms 5388 KB Output is correct
17 Correct 857 ms 5080 KB Output is correct
18 Correct 824 ms 5488 KB Output is correct
19 Correct 853 ms 5508 KB Output is correct
20 Incorrect 4 ms 2816 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 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 60 ms 7928 KB Output isn't correct
2 Halted 0 ms 0 KB -