제출 #1312165

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312165		mikolajsz	Dreaming (IOI13_dreaming)	C++20	100 / 100	53 ms	15828 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;

const int MAXN=1e5+1;
const int inf = 1e9;

int dp1[MAXN],up1[MAXN],visited[MAXN],diam,path;
vector<vector<pair<int,int>>> G(MAXN);

void dfs1(int v, int p){
	visited[v]=1;
	for(auto e: G[v]){
		int u=e.first, w=e.second;
		if(u==p) continue;
		dfs1(u,v);
		dp1[v]=max(dp1[v],dp1[u]+w);
		diam=max(diam,dp1[v]);
	}
}

void dfs2(int v, int p){
	int idx1=-1,idx2=-1,best1=0,best2=0;
	for(auto e: G[v]){
		int u=e.first,w=e.second;
		if(u==p) continue;
		if(dp1[u]+w>=best1){
			idx2=idx1;
			best2=best1;
			idx1=u;
			best1=dp1[u]+w;
		} else if(dp1[u]+w>=best2){
			idx2=u;
			best2=dp1[u]+w;
		}
	}
	for(auto e: G[v]){
		int u=e.first,w=e.second;
		if(u==p) continue;
		int best_child = (u!=idx1?best1:best2);
		up1[u] = max(up1[v],best_child)+w;
		diam = max(diam,max(up1[v]+best_child,best1+best2));
		diam = max(diam,up1[u]);
		dfs2(u,v);
	}
}

void dfs3(int v, int p){
	for(auto e: G[v]){
		int u=e.first,w=e.second;
		if(u==p) continue;
		path=min(path,max(dp1[v],up1[v]));
		dfs3(u,v);
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
	int diameter=0,ans=0;
	vector<int> components;
	for(int i=0; i<=N; i++){
		visited[i]=0;
		G[i].clear();
		dp1[i]=up1[i]=0;
	}
	for(int i=0; i<M; i++){
		A[i]++;B[i]++;
		G[A[i]].push_back({B[i],T[i]});
		G[B[i]].push_back({A[i],T[i]});
	}
	for(int v=1; v<=N; v++){
		if(!visited[v]){
			diam=0,path=inf;
			dfs1(v,0);
			dfs2(v,0);
			dfs3(v,0);
            //if(v==2){cout << "xd " << path << "\n";}
			diameter=max(diameter,diam);
            if(path==inf)path=0;
			components.push_back(path);
		}
	} // jak sie wypierdoli pozniej to ogarnij jak sa pojedyncze wierzcholki wliczane w odp czy cos bo to sie wypierdala chb
	sort(components.begin(),components.end(), greater<>());
    //for(int x: components) cout << x << " ";
    //cout << "\n";
	ans=max(components[0],diameter);
	if(components.size()>=2){
		ans=max(ans,components[0]+components[1]+L);
	}
	if(components.size()>=3){
		ans=max(ans,components[1]+components[2]+2*L);
	}
	return ans;
}

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