oj.uz

Submission #962098

# Submission time Handle Problem Language Result Execution time Memory
962098 2024-04-13T07:00:46 Z serkanrashid Dreaming (IOI13_dreaming) C++11
0 / 100
 43 ms 11384 KB 
#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+5;

struct edge
{
    int ver,dist;
    edge(){};
    edge(int vi, int di)
    {
        ver = vi;
        dist = di;
    }
};

int n;

vector<edge> g[MAXN];
int sub[MAXN],used[MAXN];

int mind;
vector<int> comp;

void clear_used()
{
    for(int i = 0; i < n; i++) used[i] = 0;
}

void dfs_dp(int beg, int gor)
{
    used[beg] = 1;
    int maxch = max(sub[beg],gor);
    mind = min(mind,maxch);
    int fir = 0, sec = 0;
    for(edge nb : g[beg])
    {
        if(!used[nb.ver])
        {
            if(nb.dist+sub[nb.ver] > fir)
            {
                sec = fir;
                fir = nb.dist+sub[nb.ver];
            }
            else if(nb.dist+sub[nb.ver] > sec)
            {
                sec = nb.dist+sub[nb.ver];
            }
        }
    }
    for(edge nb : g[beg])
    {
        if(!used[nb.ver])
        {
            int new_gor = gor;
            if(nb.dist+sub[nb.ver] == fir) new_gor = max(new_gor,sec);
            else new_gor = max(new_gor,fir);
            new_gor += nb.dist;
            dfs_dp(nb.ver,new_gor);
        }
    }
}

void dfs(int beg)
{
    used[beg] = 1;
    for(edge nb : g[beg])
    {
        if(!used[nb.ver])
        {
            dfs(nb.ver);
            sub[beg] = max(sub[beg],sub[nb.ver]+nb.dist);
        }
    }
}

int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
    n = N;
    for(int i = 0; i < M; i++)
    {
        g[A[i]].push_back({B[i],T[i]});
        g[B[i]].push_back({A[i],T[i]});
    }
    for(int i = 0; i < N; i++) if(!used[i]) dfs(i);
    clear_used();
    for(int i = 0; i < N; i++)
    {
        if(!used[i])
        {
            mind = 1e9+5;
            dfs_dp(i,0);
            comp.push_back(mind);
        }
    }
    return comp[0]+comp[1]+L;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 11384 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 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 7004 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 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

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