제출 #1216032

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1216032		elotelo966	꿈 (IOI13_dreaming)	C++20	0 / 100	37 ms	10408 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

//#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define pb push_back
#define lim 100005
//#define N 500050

typedef long long lo;

const int mod=1000000007;

int n,m;

int A[lim],B[lim],T[lim],L;

int vis[lim];

int dia_node[2],dp[lim][2];

vector<pair<int,int>> v[lim];

int dist,cev,ger;

inline void dfs(int node,int ata,int cur_dist,int kim){
	//cout<<node<<" "<<ata<<" "<<cur_dist<<" "<<kim<<" "<<dist<<endl;
	vis[node]=1;
	if(cur_dist>dist){
		dist=cur_dist;
		ger=max(ger,dist);
		dia_node[kim]=node;
	}
	for(auto go:v[node]){
		if(go.fi==ata)continue;
		dfs(go.fi,node,cur_dist+go.se,kim);
	}
}

inline void dfs2(int node,int ata,int cur_dist,int kim){
	dp[node][kim]=cur_dist;
	if(kim==1){
		cev=min(cev,max(dp[node][0],dp[node][1]));
	}
	for(auto go:v[node]){
		if(go.fi==ata)continue;
		dfs2(go.fi,node,cur_dist+go.se,kim);
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n=N;
	m=M;
	
	for(int i=0;i<m;i++){
		v[A[i]].pb({B[i],T[i]});
		v[B[i]].pb({A[i],T[i]});
	}
	
	vector<int> ans;
	
	for(int i=0;i<n;i++){
		if(vis[i])continue;
		dist=-1;
		cev=LLONG_MAX;
		dfs(i,-1,0,0);
		dist=-1;
		dfs(dia_node[0],-1,0,1);
		//cout<<dia_node[0]<<" "<<dia_node[1]<<endl;
		dfs2(dia_node[0],-1,0,0);
		dfs2(dia_node[1],-1,0,1);
		//cout<<cev<<endl;
		ans.pb(cev);
	}
	
	sort(ans.rbegin(),ans.rend());
		
	if(ans.size()==1){
		ger=max(ger,ans[0]);
	}
	else if(ans.size()==2){
		ger=max(ger,ans[0]+ans[1]+L);
	}
	else{
		ger=max({ger,ans[0]+ans[1]+L,ans[1]+ans[2]+2*L});
	}
	
	return ger;
}

//~ int32_t main(){
	//~ faster
	//~ cin>>n>>m;
	
	//~ cin>>L;
	
	//~ for(int i=0;i<m;i++){
		//~ cin>>A[i]>>B[i]>>T[i];
		//~ v[A[i]].pb({B[i],T[i]});
		//~ v[B[i]].pb({A[i],T[i]});
	//~ }
	
	//~ vector<int> ans;
	
	//~ for(int i=0;i<n;i++){
		//~ if(vis[i])continue;
		//~ dist=-1;
		//~ cev=LLONG_MAX;
		//~ dfs(i,-1,0,0);
		//~ dist=-1;
		//~ dfs(dia_node[0],-1,0,1);
		//~ //cout<<dia_node[0]<<" "<<dia_node[1]<<endl;
		//~ dfs2(dia_node[0],-1,0,0);
		//~ dfs2(dia_node[1],-1,0,1);
		//~ //cout<<cev<<endl;
		//~ ans.pb(cev);
	//~ }
	
	//~ sort(ans.rbegin(),ans.rend());
		
	//~ if(ans.size()==1){
		//~ ger=max(ger,ans[0]);
	//~ }
	//~ else if(ans.size()==2){
		//~ ger=max(ger,ans[0]+ans[1]+L);
	//~ }
	//~ else{
		//~ ger=max({ger,ans[0]+ans[1]+L,ans[1]+ans[2]+2*L});
	//~ }
	
	//~ cout<<ger<<'\n';
	
	//~ return 0;
//~ }

컴파일 시 표준 에러 (stderr) 메시지

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:71:21: warning: overflow in conversion from 'long long int' to 'int' changes value from '9223372036854775807' to '-1' [-Woverflow]
   71 |                 cev=LLONG_MAX;
      |                     ^~~~~~~~~

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