제출 #879218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
879218		mahmoudbadawy	Dreaming (IOI13_dreaming)	C++17	100 / 100	73 ms	27916 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

vector< pair<int,int> > adj[100005];
int vis[100005],mem[100005],mem2[100005];
int hi[100005],id[100005],maxi[100005];
int n;


void dfs(int node,int pa,int h)
{
	vis[node]=1;
	hi[node]=h;
	for(int i=0;i<adj[node].size();i++)
	{
		if(adj[node][i].F==pa)
			continue;
		dfs(adj[node][i].F,node,h+adj[node][i].S);
		mem[node]=max(mem[node],mem[adj[node][i].F]+adj[node][i].S);
	}
}

void dfs2(int node,int pa,int maxi,int idc)
{
	//cout << node << " " << pa << " " << maxi << endl;
	vis[node]=0; id[node]=idc;
	vector<int> ch;
	for(int i=0;i<adj[node].size();i++)
	{
		if(adj[node][i].F==pa)
			continue;
		ch.push_back(mem[adj[node][i].F]+adj[node][i].S);
	}
	//cout << "OK " << ch.size() << endl;
	sort(ch.begin(),ch.end()); reverse(ch.begin(),ch.end());
	mem2[node]=max(max(maxi,hi[node]),ch.size()?ch[0]:0); 
	for(int i=0;i<adj[node].size();i++)
	{
		if(adj[node][i].F==pa)
			continue;
		int oth=(ch[0]==mem[adj[node][i].F]+adj[node][i].S?(ch.size()>1?ch[1]:0):ch[0]);
		dfs2(adj[node][i].F,node,max(maxi,oth)+adj[node][i].S,idc);
	}
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n=N;
    for(int i=0;i<M;i++)
    {
    	adj[A[i]].push_back({B[i],T[i]});
    	adj[B[i]].push_back({A[i],T[i]});
    }
    for(int i=0;i<N;i++)
    {
    	if(!vis[i])
    		dfs(i,-1,0);
    }
    int idc=1;
    for(int i=0;i<N;i++)
    {
    	if(vis[i])
    		dfs2(i,-1,0,idc++);
    }
    for(int i=0;i<N;i++)
    	maxi[i]=(1<<30);
    for(int i=0;i<N;i++)
    	maxi[id[i]]=min(maxi[id[i]],mem2[i]);
    vector<int> v;
    for(int i=1;i<idc;i++)
    	v.push_back(maxi[i]);
    sort(v.begin(),v.end()); reverse(v.begin(),v.end());
    int maxr=0;
    for(int i=0;i<N;i++)
    	maxr=max(maxr,mem2[i]);
    if(v.size()==1)
    	return maxr;
    else if(v.size()==2)
    	return max(maxr,v[0]+L+v[1]);
    return max(maxr,max(v[0]+L+v[1],2*L+v[1]+v[2]));
}

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

dreaming.cpp: In function 'void dfs(int, int, int)':
dreaming.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i=0;i<adj[node].size();i++)
      |              ~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int, int, int)':
dreaming.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(int i=0;i<adj[node].size();i++)
      |              ~^~~~~~~~~~~~~~~~~
dreaming.cpp:41:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i=0;i<adj[node].size();i++)
      |              ~^~~~~~~~~~~~~~~~~

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