oj.uz

Submission #469054

# Submission time Handle Problem Language Result Execution time Memory
469054 2021-08-30T14:33:27 Z jazzup Dreaming (IOI13_dreaming) C++14
0 / 100
 82 ms 30268 KB 
#include "dreaming.h"
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>

using namespace std;

int dis1[100010],dis2[100010];
bool visited[100010];
vector<pair<int,int> > v[100010],pb,pbb;
vector<int> pa,nl,len,len2;
queue<int> q;
pair<int,int> tmp;

int a[100010],b[100010],c[100010];
bool shd;

void dfs(pair<int,int> n){
	visited[n.first]=true;
	nl.push_back(n.first);

	if(dis2[n.first]==n.second){
		pbb.push_back(n);
		double targ=n.second/2.0;
		double dd=targ;
		int pu;
		for(int i=0;i<nl.size();i++){
			double diff=abs((double)dis2[nl[i]]-targ);
			if(diff<=dd){
				dd=diff;
				pu=max(dis2[nl[i]],n.second-dis2[nl[i]]);
			}
		}
		if(!shd){
			len.push_back(pu);
			shd=true;
			tmp=n;
		}
		else if(pu<len.back()){
			len.pop_back();
			len.push_back(pu);
			tmp=n;
		}
	}

	for(int i=0;i<v[n.first].size();i++){
		if(!visited[v[n.first][i].first]){
			dis2[v[n.first][i].first]=dis2[n.first]+v[n.first][i].second;
			dfs(make_pair(v[n.first][i].first,n.second));
		}
	}
	nl.pop_back();
	// dis2[n.first]=0;
}

void dfs2(pair<int,int> n){
	visited[n.first]=true;
	nl.push_back(n.first);

	if(dis2[n.first]==n.second){
		pbb.push_back(n);
		double targ=n.second/2.0;
		double dd=targ;
		int pu;
		for(int i=0;i<nl.size();i++){
			double diff=abs((double)dis2[nl[i]]-targ);
			if(diff<=dd){
				dd=diff;
				pu=max(dis2[nl[i]],n.second-dis2[nl[i]]);
			}
		}
		if(!shd){
			len2.push_back(pu);
			shd=true;
			tmp=n;
		}
		else if(pu<len2.back()){
			len2.pop_back();
			len2.push_back(pu);
			tmp=n;
		}
	}

	for(int i=0;i<v[n.first].size();i++){
		if(!visited[v[n.first][i].first]){
			dis2[v[n.first][i].first]=dis2[n.first]+v[n.first][i].second;
			dfs(make_pair(v[n.first][i].first,n.second));
		}
	}
	nl.pop_back();
	// dis2[n.first]=0;
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]){
	for(int i=0;i<n;i++){
		dis1[i]=-1;
	}

	for(int i=0;i<m;i++){
		v[a[i]].push_back(make_pair(b[i],t[i]));
		v[b[i]].push_back(make_pair(a[i],t[i]));
	}

	for(int i=0;i<n;i++){
		if(dis1[i]==-1){
			dis1[i]=0;
			q.push(i);
			visited[i]=true;	

			int mxd=0,nd=i;

			while(!q.empty()){
				int cur=q.front();
				if(dis1[cur]>mxd){
					mxd=dis1[cur];
					nd=cur;
				}
				q.pop();
				for(int i=0;i<v[cur].size();i++){
					if(!visited[v[cur][i].first]){
						q.push(v[cur][i].first);
						dis1[v[cur][i].first]=dis1[cur]+v[cur][i].second;
						visited[v[cur][i].first]=true;
					}
				}
			}
			pa.push_back(nd);
		}
	}

	for(int i=0;i<n;i++){
		dis1[i]=-1;
		visited[i]=false;
	}

	for(int i=0;i<pa.size();i++){
		dis1[pa[i]]=0;
		q.push(pa[i]);
		visited[pa[i]]=true;	

		int mxd=0,nd=i;

		while(!q.empty()){
			int cur=q.front();
			if(dis1[cur]>mxd){
				mxd=dis1[cur];
				nd=cur;
			}
			q.pop();
			for(int i=0;i<v[cur].size();i++){
				if(!visited[v[cur][i].first]){
					q.push(v[cur][i].first);
					dis1[v[cur][i].first]=dis1[cur]+v[cur][i].second;
					visited[v[cur][i].first]=true;
				}
			}
		}
		pb.push_back(make_pair(nd,mxd));
	}

	for(int i=0;i<n;i++){
		dis2[i]=-1;
		visited[i]=false;
	}

	for(int i=0;i<pb.size();i++){
		dis2[pb[i].first]=0;
		shd=false;
		dfs(pb[i]);
	}

	for(int i=0;i<n;i++){
		dis2[i]=-1;
		visited[i]=false;
	}

	for(int i=0;i<pbb.size();i++){
		dis2[pb[i].first]=0;
		shd=false;
		dfs2(pbb[i]);
	}

	for(int i=0;i<len.size();i++){
		len[i]=min(len[i],len2[i]);
	}

	sort(len.begin(),len.end());

	int ml=-1;

	for(int i=0;i<n;i++){
		if(dis2[i]>ml){
			ml=dis2[i];
		}
	}

	int yo=n-m;

	int ans=-1;

	if(yo>=3){
		ans=max(len[yo-1]+len[yo-2]+l,len[yo-3]+len[yo-2]+2*l);
	}

	else if(yo==2){
		ans=len[yo-1]+len[yo-2]+l;
	}

	ans=max(ans,ml);
	// printf("%lld\n",yo);
    return ans;
}

Compilation message

dreaming.cpp: In function 'void dfs(std::pair<int, int>)':
dreaming.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int i=0;i<nl.size();i++){
      |               ~^~~~~~~~~~
dreaming.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=0;i<v[n.first].size();i++){
      |              ~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(std::pair<int, int>)':
dreaming.cpp:67:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for(int i=0;i<nl.size();i++){
      |               ~^~~~~~~~~~
dreaming.cpp:86:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for(int i=0;i<v[n.first].size();i++){
      |              ~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for(int i=0;i<v[cur].size();i++){
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp:138:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |  for(int i=0;i<pa.size();i++){
      |              ~^~~~~~~~~~
dreaming.cpp:152:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |    for(int i=0;i<v[cur].size();i++){
      |                ~^~~~~~~~~~~~~~
dreaming.cpp:168:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |  for(int i=0;i<pb.size();i++){
      |              ~^~~~~~~~~~
dreaming.cpp:179:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |  for(int i=0;i<pbb.size();i++){
      |              ~^~~~~~~~~~~
dreaming.cpp:185:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |  for(int i=0;i<len.size();i++){
      |              ~^~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 30268 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5196 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 30268 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 16024 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5196 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 30268 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -