oj.uz

Submission #805678

# Submission time Handle Problem Language Result Execution time Memory
805678 2023-08-03T20:13:24 Z Mouad_ouj Dreaming (IOI13_dreaming) C++17
0 / 100
 1000 ms 13064 KB 
#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=max(dia[z-1]+dia[z-2]+l,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 );
}*/

Compilation message

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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 13064 KB Output is correct
2 Correct 36 ms 13048 KB Output is correct
3 Correct 23 ms 8608 KB Output is correct
4 Correct 5 ms 2132 KB Output is correct
5 Correct 4 ms 1364 KB Output is correct
6 Correct 10 ms 3132 KB Output is correct
7 Incorrect 1 ms 260 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 13064 KB Output is correct
2 Correct 36 ms 13048 KB Output is correct
3 Correct 23 ms 8608 KB Output is correct
4 Correct 5 ms 2132 KB Output is correct
5 Correct 4 ms 1364 KB Output is correct
6 Correct 10 ms 3132 KB Output is correct
7 Incorrect 1 ms 260 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 6488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 13064 KB Output is correct
2 Correct 36 ms 13048 KB Output is correct
3 Correct 23 ms 8608 KB Output is correct
4 Correct 5 ms 2132 KB Output is correct
5 Correct 4 ms 1364 KB Output is correct
6 Correct 10 ms 3132 KB Output is correct
7 Incorrect 1 ms 260 KB Output isn't correct
8 Halted 0 ms 0 KB -