Submission #761609

#	Time	Username	Problem	Language	Result	Execution time	Memory
761609		KN200711	Dreaming (IOI13_dreaming)	C++14	100 / 100	89 ms	29340 KiB

dreaming

#include "dreaming.h"
# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
using namespace std;

// idenya dfs dua kali
// yang pertama subtree normal, yang kedua dari luar subtree
vector< pair<int, int> > edge[100001];
bool vis[100001];
int ins[100001];
vector<int> pref[100001], suff[100001];

void dfs(int a, int pr) {
	vis[a] = 1;
	ins[a] = 0;
	for(int k=0;k<edge[a].size();k++) {
		if(edge[a][k].fi == pr) continue;
		dfs(edge[a][k].fi, a);
		ins[a] = max(ins[edge[a][k].fi] + edge[a][k].se, ins[a]);
	}
}

int cek, ct;

void fn(int a, int pr, int bf) {
//	cout<<"a : "<<a<<" "<<bf<<" "<<ins[a]<<endl;
	cek = min(cek, max(bf, ins[a]));
	ct = max(ct, max(bf, ins[a]));
	pref[a].resize(edge[a].size());
	suff[a].resize(edge[a].size());
	for(int k=0;k<edge[a].size();k++) {
		if(edge[a][k].fi == pr) {
			if(k == 0) pref[a][k] = 0;
			else pref[a][k] = pref[a][k - 1];	
		} else {
			if(k == 0) pref[a][k] = ins[edge[a][k].fi] + edge[a][k].se;
			else pref[a][k] = max(pref[a][k-1], ins[edge[a][k].fi] + edge[a][k].se);
		}
	}
	for(int k=edge[a].size() - 1;k>=0;k--) {
		if(edge[a][k].fi == pr) {
			if(k == edge[a].size() - 1) suff[a][k] = 0;
			else suff[a][k] = suff[a][k + 1];	
		} else {
			if(k == edge[a].size() - 1) suff[a][k] = ins[edge[a][k].fi] + edge[a][k].se;
			else suff[a][k] = max(suff[a][k+1], ins[edge[a][k].fi] + edge[a][k].se);
		}
	}
	
	for(int k=0;k<edge[a].size();k++) {
		if(edge[a][k].fi == pr) continue;
		
		int mx = 0;
		if(k > 0) mx = max(mx, pref[a][k - 1]);
		if(k + 1 < edge[a].size()) mx = max(mx, suff[a][k + 1]);
		
	//	cout<<"AA : "<<edge[a][k].fi<<" "<<mx<<" "<<edge[a][k].se<<endl;
		
		fn(edge[a][k].fi, a, max(mx, bf) + edge[a][k].se);
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for(int k=0;k<N;k++) {
		edge[k].clear();
		vis[k] = 0;
	}
	for(int i=0;i<M;i++) {
		edge[A[i]].push_back(make_pair(B[i], T[i]));
		edge[B[i]].push_back(make_pair(A[i], T[i]));
	}
	vector<int> P;
	P.clear();
	int ans = 0;
	for(int i=0;i<N;i++) {
		if(!vis[i]) {
			cek = 2e9;
			ct = 0;
			dfs(i, -1);
			fn(i, -1, 0);
			ans = max(ans, ct);
			P.push_back(cek);
		//	cout<<cek<<endl;
		//	cout<<ins[i]<<endl;
		//	cout<<i<<" "<<cek<<endl;
		}
	}
	sort(P.begin(), P.end());
	if(P.size() == 1) return max(P[0], ans);
	else if(P.size() == 2) return max(P[0] + P[1] + L, ans);
	else {
		int t1 = P.back() + L + P[P.size() - 2];
		int t2 = P[P.size() - 2] + L + L + P[P.size() - 3];
		return max(t1, max(t2, ans));
	}
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:18: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]
   18 |  for(int k=0;k<edge[a].size();k++) {
      |              ~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'void fn(int, int, int)':
dreaming.cpp:33: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]
   33 |  for(int k=0;k<edge[a].size();k++) {
      |              ~^~~~~~~~~~~~~~~
dreaming.cpp:44:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |    if(k == edge[a].size() - 1) suff[a][k] = 0;
      |       ~~^~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:47:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    if(k == edge[a].size() - 1) suff[a][k] = ins[edge[a][k].fi] + edge[a][k].se;
      |       ~~^~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:52: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]
   52 |  for(int k=0;k<edge[a].size();k++) {
      |              ~^~~~~~~~~~~~~~~
dreaming.cpp:57:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   if(k + 1 < edge[a].size()) mx = max(mx, suff[a][k + 1]);
      |      ~~~~~~^~~~~~~~~~~~~~~~

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