Submission #342804

#	Time	Username	Problem	Language	Result	Execution time	Memory
342804		wwdd	Dreaming (IOI13_dreaming)	C++14	100 / 100	109 ms	17260 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> al;
typedef vector<int> vi;
typedef vector<vi> vvi;

ii dfa(int u, int p, al& g, vii& pa) {
	ii res = {u,0};
	for(int i=0;i<g[u].size();i++) {
		int v = g[u][i].first;
		int dist = g[u][i].second;
		if(v == p) {
			continue;
		}
		pa[v] = {u,dist};
		ii dv = dfa(v,u,g,pa);
		if(dv.second+dist > res.second) {
			res = {dv.first,dv.second+dist};
		}
	}
	return res;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	al g;
	g.assign(N,vii());
	for(int i=0;i<M;i++) {
		int a = A[i];
		int b = B[i];
		g[a].push_back({b,T[i]});
		g[b].push_back({a,T[i]});
	}
	vii pa(N,{-1,-1});
	vi rep;
	vii dia;
	int res = 0;
	for(int i=0;i<N;i++) {
		if(pa[i].first == -1) {
			ii va = dfa(i,i,g,pa);
			int mv = va.first;
			pa[mv] = {mv,0};
			ii vb = dfa(mv,mv,g,pa);
			rep.push_back(mv);
			dia.push_back(vb);
			res = max(res,vb.second);
		}
	}
	vi wa;
	for(int i=0;i<rep.size();i++) {
		int u = dia[i].first;
		int da = 0;
		int db = dia[i].second;
		int dv = db;
		while(pa[u].first != u) {
			da += pa[u].second;
			db -= pa[u].second;
			u = pa[u].first;
			dv = min(dv,max(da,db));
		}
		wa.push_back(dv);
	}
	sort(wa.rbegin(),wa.rend());
	res = max(res,wa.front());
	if(wa.size() > 1) {
		res = max(res,wa[0]+wa[1]+L);
	}
	if(wa.size() > 2) {
		res = max(res,wa[1]+wa[2]+2*L);
	}
    return res;
}

Compilation message (stderr)

dreaming.cpp: In function 'ii dfa(int, int, al&, vii&)':
dreaming.cpp:13: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]
   13 |  for(int i=0;i<g[u].size();i++) {
      |              ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:52:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i=0;i<rep.size();i++) {
      |              ~^~~~~~~~~~~

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