Submission #94186

#	Time	Username	Problem	Language	Result	Execution time	Memory
94186		fjzzq2002	Dreaming (IOI13_dreaming)	C++14	100 / 100	76 ms	14064 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef pair<int,int> pii;
#define fi first
#define se second
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 666666
int ff[SZ]; Edgc
int gf(int x) {return (~ff[x])?ff[x]=gf(ff[x]):x;}
void uni(int a,int b)
{
	a=gf(a),b=gf(b);
	if(a==b) throw "GG";
	ff[a]=b;
}
int ca=0;
pii mx;
vector<int> ve;
int fa[SZ],fe[SZ],d1[SZ],d2[SZ],*op;
void dfs(int x,int d=0)
{
	ve.pb(x);
	op[x]=d; mx=max(mx,pii(d,x));
	for esb(x,e,b) if(b!=fa[x])
		fa[b]=x,fe[b]=vc[e],dfs(b,d+vc[e]);
}
int work(int t)
{
	auto g=ve;
	mx=pii(-1,0);
	ve.clear();
	fa[t]=-1; op=d1; dfs(t);
	ca=max(ca,mx.fi);
	int u=mx.se;
	mx=pii(-1,0);
	ve.clear();
	fa[u]=-1; op=d1; dfs(u);
	int v=mx.se;
	ve.clear();
	fa[v]=-1; op=d2; dfs(v);
	ca=max(ca,mx.fi);
	int aa=mx.fi;
	for(auto g:ve)
		aa=min(aa,max(d1[g],d2[g]));
	return aa;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    ca=0;
	memset(ff,-1,sizeof ff);
    for(int i=0;i<M;++i)
    	adde(A[i],B[i],T[i]),uni(A[i],B[i]);
    vector<int> v;
    for(int i=0;i<N;++i)
    	if(gf(i)==i) v.pb(work(i));
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    for(int i=1;i<v.size();++i) v[i]+=L;
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    if(v.size()>=2) ca=max(ca,v[0]+v[1]);
	return ca;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:60:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<v.size();++i) v[i]+=L;
                 ~^~~~~~~~~

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