Submission #805707

#	Time	Username	Problem	Language	Result	Execution time	Memory
805707		Mouad_ouj	Dreaming (IOI13_dreaming)	C++17	59 / 100	1086 ms	17472 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int> >> adj;
vector<bool> vis;
vector<vector<int> > t;
vector<int> d,ty;
int n,m,l;
void dfs(int node,int f)
{
    vis[node]=true;
    int k=adj[node].size();
    for(int x=0;x<k;x++)
    {
        int to=adj[node][x].first;
        if(!vis[to])
        {
        t[f].push_back(to);    
        dfs(to,f);
        }
    }
}
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 cn=t[y].size();
    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=0;x<cn;x++)
    {
        if(cur<=dis[t[y][x]] && t[y][x]!=y)
        {
            a=t[y][x];
            cur=dis[t[y][x]];
        }
    }    
    vis.assign(n+1,false);
    dfs3(a,disa);
    cur=0;
    for(int x=0;x<cn;x++)
    {
        if(cur<disa[t[y][x]] && t[y][x]!=a)
        {
            b=t[y][x];
            cur=disa[t[y][x]];
        }
    }
    vis.assign(n+1,false);
    dfs3(b,disb);
    int ans=disb[a];
    for(int x=0;x<cn;x++)
        ans=min(ans,max(disa[t[y][x]],disb[t[y][x]]));
    d.push_back(disa[b]);
    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);
    t.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])
        {
        t[x].push_back(x);    
        dfs(x,x);
        ty.push_back(x);
        }
    }
    int z=ty.size();
    int dia[z]={0};
    for(int x=0;x<z;x++)
        dia[x]=get(ty[x]);
    int ans=0,ans1=0,mx=dia[0],mx2=0,mx3=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]);
    for(int x=1;x<z;x++)
    {
        if(dia[x]>=mx)
        {
            mx3=mx2;
            mx2=mx;
            mx=dia[x];
        }
        else if(dia[x]>=mx2)
        {
            mx3=mx2;
            mx2=dia[x];
        }
        else if(dia[x]>mx3)
        mx3=dia[x];
    }
    if(z-2>=0)
    ans1=mx+mx2+l;
    if(z-3>=0)
    ans1=max(ans1,mx3+mx2+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 );
}*/

Compilation message (stderr)

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

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