Submission #94185

#	Time	Username	Problem	Language	Result	Execution time	Memory
94185		fjzzq2002	Dreaming (IOI13_dreaming)	C++14	18 / 100	395 ms	65536 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];
void dfs(int x,int d=0)
{
	ve.pb(x);
	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)
{
	ve.clear(); fa[t]=-1; dfs(t);
	auto g=ve; int mi=2e9;
	for(auto s:g)
		mx.fi=-1,fa[s]=-1,dfs(s),
		ca=max(ca,mx.fi),
		mi=min(mi,mx.fi);
	return mi;
}
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;
}

//prototype

Compilation message (stderr)

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

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