oj.uz

Submission #805506

# Submission time Handle Problem Language Result Execution time Memory
805506 2023-08-03T17:15:06 Z Mouad_ouj Dreaming (IOI13_dreaming) C++17
0 / 100
 37 ms 15436 KB 
#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int> >> adj;
vector<bool> vis;
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 travelTime(int ne,int me,int le,int u[],int v[],int t[])
{
    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,t[x]));
        adj[v[x]+1].push_back(make_pair(u[x]+1,t[x]));
    }
    int c=0;
    dfs(1);
    for(int x=2;x<=n;x++)
    {
        if(!vis[x])
        {
        c=x;
        break;
        }
    }
    int cur=0,a=0,b=0,dis[n+1]={0},disa[n+1]={0},disb[n+1]={0},dis2[n+1]={0},disd[n+1]={0},dise[n+1]={0};
    vis.assign(n+1,false);
    dfs3(1,dis);
    for(int x=1;x<=n;x++)
    {
        if(cur<dis[x] && x!=1)
        {
            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);
    vis.assign(n+1,false);
    dfs3(c,dis2);
    int e=0,d=0;
    cur=0;
    for(int x=1;x<=n;x++)
    {
        if(cur<dis2[x] && x!=c)
        {
            e=x;
            cur=dis2[x];
        }
    }
    vis.assign(n+1,false);
    dfs3(e,dise);
    cur=0;
    for(int x=1;x<=n;x++)
    {
        if(cur<dise[x] && x!=e)
        {
            d=x;
            cur=dise[x];
        }
    }
    vis.assign(n+1,false);
    dfs3(d,disd);
    //cout<<a-1<<" "<<b-1<<" "<<e-1<<" "<<d-1<<endl;
    int ans1=disb[a],ans2=dise[d];
    for(int x=1;x<=n;x++)
    {
        //cout<<disa[x]<<endl;
        if(disa[x]!=0 || disb[x]!=0)
        ans1=min(ans1,max(disa[x],disb[x]));
        else if(dise[x]!=0 || disd[x]!=0)
        ans2=min(ans2,(max(dise[x],disd[x])));
    }
    if(n==1)
    return 0;
    else
    return ans1+ans2+l;
}
/*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 );
}*/

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 15436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 15436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 7360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 15436 KB Output isn't correct
2 Halted 0 ms 0 KB -