Submission #56445

#	Time	Username	Problem	Language	Result	Execution time	Memory
56445		hamzqq9	Dreaming (IOI13_dreaming)	C++14	100 / 100	119 ms	15216 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
#define lf double
#define ll long long
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 1002000000
#define LOG 20
#define magic 100
#define MAX 100005
#define KOK 350
#define EPS 0.000000000001
#define pw(x) (1<<(x))
#define PI 3.1415926535
using namespace std;

vector< pair<int,short int> > v[MAX];
int mx[4],deep[MAX];
int cnt,Dcnt;
bool vis[MAX];

void up(int val) {

	mx[2]=val;

	for(int i=2;i>0;i--) {

		if(mx[i]>mx[i-1]) swap(mx[i],mx[i-1]);

	}

}

void dfs3(int node,int ata) {

	deep[node]=0;

	for(ii i:v[node]) {

		if(i.st==ata) continue ;

		dfs3(i.st,node);

		if(node==cnt) {

			up(deep[i.st]+i.nd);
		
		}
		else {

			umax(deep[node],deep[i.st]+i.nd);

		}

 	}

}

void dfs2(int node,int ata,int up_max) {

	int Mx[2]={0,0};

	int MX=max(deep[node],up_max);

	if(MX<Dcnt) {

		Dcnt=MX;
		cnt=node;

	}

	for(ii i:v[node]) {

		if(i.st==ata) continue ;

		Mx[1]=max(Mx[1],deep[i.st]+i.nd);

		if(Mx[1]>Mx[0]) swap(Mx[1],Mx[0]);

	}

	for(ii i:v[node]) {

		if(i.st==ata) continue ;

		int send=(Mx[Mx[0]==deep[i.st]+i.nd]);

		dfs2(i.st,node,max(up_max,send)+i.nd);

	}

}

void dfs1(int node,int ata) {

	deep[node]=0;
	vis[node]=true;

	for(ii i:v[node]) {

		if(i.st==ata) continue ;

		dfs1(i.st,node);

		umax(deep[node],deep[i.st]+i.nd);

	}

}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    
	vector<ii> CMP;

	for(int i=0;i<M;i++) {

		v[A[i]].pb({B[i],T[i]});
		v[B[i]].pb({A[i],T[i]});

	}

	for(int i=0;i<N;i++) {

		if(!vis[i]) {

			dfs1(i,-1);

			Dcnt=inf;

			dfs2(i,-1,0);

		//	printf("%d %d\n",Dcnt,cnt);

			mx[0]=mx[1]=0;

			dfs3(cnt,-1);

		//	printf("%d %d\n",mx[0],mx[1]);

			CMP.pb({mx[0],mx[1]});

		}

	}

	int ans=0;

	sort(all(CMP),greater<ii>());

	mx[0]=mx[1]=-inf;

	for(int i=0;i<sz(CMP);i++) {

		umax(ans,CMP[i].st+CMP[i].nd);

		if(i==0) {

			up(CMP[i].st);

		}
		else {

			up(CMP[i].st+L);

		}

	}

	umax(ans,mx[0]+mx[1]);

	return ans;

}
/*
int main() {

	freopen("read.txt","r",stdin);

	int a[55],b[55],t[55],L,N,M;

	scanf("%d %d %d",&N,&M,&L);

	for(int i=0;i<M;i++) {

		scanf("%d %d %d",&a[i],&b[i],&t[i]);

	}

	printf("%d\n",travelTime(N,M,L,a,b,t));

}*/

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