Submission #943185

#	Time	Username	Problem	Language	Result	Execution time	Memory
943185		PenguinsAreCute	Dreaming (IOI13_dreaming)	C++17	100 / 100	52 ms	16072 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#define fi first
#define se second
#define pb push_back
#define REP(i,a,b) for(int i=a;i<b;i++)
int dist[121010], par[121010]; // 42 days to go, 42 lines of code.
vector<int> cc;
vector<ii> adj[121010];
void dfs(int x, int p, bool ins) {
	par[x]=p; if(ins) cc.pb(x);
	for(auto i: adj[x]) if(i.fi!=p) {dist[i.fi]=dist[x]+i.se; dfs(i.fi,x,ins);}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	vector<int> cenTimes; int maxD=0;
	REP(i,0,M) {
		adj[A[i]].pb(ii(B[i],T[i]));
		adj[B[i]].pb(ii(A[i],T[i]));
	}
	REP(i,0,N) if(dist[i]==0) {
		cc.clear();
		dfs(i,-1,1);
		ii far=ii(0,0);
		for(auto j: cc) far=max(far,ii(dist[j],j));
		int pt1=far.se;
		dist[pt1]=0;
		dfs(pt1,-1,0);
		far=ii(0,0);
		for(auto j: cc) far=max(far,ii(dist[j],j));
		maxD=max(maxD,far.fi);
		int cnt=0;
		while(far.se!=pt1&&dist[far.se]+dist[par[far.se]]>far.fi) far.se=par[far.se];
		cenTimes.pb(max(dist[far.se],far.fi-dist[far.se]));
		dist[pt1]=420;
	}
	sort(cenTimes.begin(),cenTimes.end(),greater<int>());
	if(cenTimes.size()>=2) maxD=max(maxD,cenTimes[0]+cenTimes[1]+L);
	if(cenTimes.size()>=3) maxD=max(maxD,cenTimes[1]+cenTimes[2]+2*L);
	return maxD;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:33:7: warning: unused variable 'cnt' [-Wunused-variable]
   33 |   int cnt=0;
      |       ^~~

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