제출 #805681

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
805681		Mouad_ouj	꿈 (IOI13_dreaming)	C++17	47 / 100	1081 ms	14304 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int> >> adj;
vector<bool> vis;
vector<int> t,d;
int n,m,l;
void dfs(int node)
{
    vis[node]=true;
    int k=adj[node].size();
    for(int x=0;x<k;x++)
    {
        int to=adj[node][x].first;
        if(!vis[to])
        dfs(to);
    }
}
void dfs3(int node,int dis[])
{
    vis[node]=true;
    int k=adj[node].size();
    for(int x=0;x<k;x++)
    {
        int to=adj[node][x].first;
        if(!vis[to])
        {
        dis[to]=dis[node]+adj[node][x].second;    
        dfs3(to,dis);
        }
    }
}
int get(int y)
{
    int dis[n+1]={0},disa[n+1]={0},disb[n+1]={0},a=0,b=0,cur=0;
    vis.assign(n+1,false);
    if(adj[y].size()!=0)
    dfs3(y,dis);
    else 
    return 0;
    for(int x=1;x<=n;x++)
    {
        if(cur<=dis[x] && x!=y)
        {
            a=x;
            cur=dis[x];
        }
    }    
    vis.assign(n+1,false);
    dfs3(a,disa);
    cur=0;
    for(int x=1;x<=n;x++)
    {
        if(cur<disa[x] && x!=a)
        {
            b=x;
            cur=disa[x];
        }
    }
    vis.assign(n+1,false);
    dfs3(b,disb);
    int ans=disb[a];
    for(int x=1;x<=n;x++)
    {
        if(disa[x]!=0 || disb[x]!=0)
        ans=min(ans,max(disa[x],disb[x]));
    }
    d.push_back(disb[a]);
    return ans;
}
int travelTime(int ne,int me,int le,int u[],int v[],int te[])
{
    n=ne;m=me;l=le;
    adj.resize(n+1);
    vis.assign(n+1,false);
    for(int x=0;x<m;x++)
    {
        adj[u[x]+1].push_back(make_pair(v[x]+1,te[x]));
        adj[v[x]+1].push_back(make_pair(u[x]+1,te[x]));
    }
    int c=0;
    for(int x=1;x<=n;x++)
    {
        if(!vis[x])
        {
        dfs(x);
        t.push_back(x);
        }
    }
    int z=t.size();
    int dia[z]={0};
    for(int x=0;x<z;x++)
        dia[x]=get(t[x]);
    int ans=0;
    /*for(int x=0;x<z;x++)
    cout<<t[x]<<" "<<dia[x]<<endl;*/
    for(int x=0;x<d.size();x++)
    ans=max(ans,d[x]);
    sort(dia,dia+z);
    int ans1=dia[z-1]+dia[z-2]+l;
  	if(z-3>=0)
    ans1=max(ans1,dia[z-2]+dia[z-3]+2*l);
    return max(ans1,ans);
}    
/*int main()
{
    int ne,me,le;
    cin>>ne>>me>>le;
    int te[me],ae[me],be[me];
    for(int x=0;x<me;x++)
    cin>>ae[x]>>be[x]>>te[x];
    //for(int x=0;x<me;x++)
    //ae[x]++,be[x]++;
    cout<<travelTime(ne, me, le, ae , be , te );
}*/

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

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int x=0;x<d.size();x++)
      |                 ~^~~~~~~~~
dreaming.cpp:81:9: warning: unused variable 'c' [-Wunused-variable]
   81 |     int c=0;
      |         ^

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