oj.uz

Submission #1078195

# Submission time Handle Problem Language Result Execution time Memory
1078195 2024-08-27T13:50:56 Z clementine Dreaming (IOI13_dreaming) C++17
0 / 100
 34 ms 14940 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll distances[100005], dist2[100005];
vector<pair<int , int>> graph[100005];
bool visited[100005], vis2[100005];
ll compmax = -1, compmax2 = -1;
int compmaxnode = -1, compmaxn2 = -1;
int parent[100005];
ll pardist[100005];
void dfs(int u)
{
    visited[u] = true;
    if(compmax < distances[u])
    {
        compmax = distances[u];
        compmaxnode = u;
    }
    for(auto v: graph[u])
    {
        if(!visited[v.second])
        {
            distances[v.second] = distances[u] + v.first;
            dfs(v.second);
        }
    }
}


void dfs2(int u)
{
    vis2[u] = true;
    //cout << u << "is here \n";
    if(compmax2 < dist2[u])
    {
        compmax2 = dist2[u];
        compmaxn2 = u;
    }
    for(auto v: graph[u])
    {
        //cout << v.second << " thought " <<  vis2[v.second] << '\n';
        if(!vis2[v.second])
        {
            parent[v.second] = u;
            pardist[v.second] = v.first;
            dist2[v.second] = dist2[u] + v.first;
            dfs2(v.second);
        }
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {

    for(int i = 0; i < M; i++)
    {
        graph[A[i]].push_back({T[i], B[i]});
        graph[B[i]].push_back({T[i], A[i]});
    }
    vector<ll> mids, diameters;
    for(int i = 0; i < N; i ++)
    {
        if(!visited[i])
        {
            //cout << i <<" this is i \n";
            compmax = -1, compmaxnode = -1;
            compmax2 = -1, compmaxn2 = -1;
            dfs(i);
            //cout << compmaxnode << " s \n";
            parent[compmaxnode] = -1;
            dfs2(compmaxnode);
            //cout << compmaxn2 << " e \n";
            diameters.push_back(compmax2);
            ll curdist = 0, prevcurdist = -1;;
            while(compmax2 - curdist > curdist)
            {
                prevcurdist = curdist;
                curdist += pardist[compmaxn2];
                compmaxn2 = parent[compmaxn2];
                //cout << curdist << " also " << compmaxn2 << '\n';
            }
            ll a ;
            if(compmax - curdist == curdist)
            {
                a = curdist;
            }
            else 
                a = min(curdist, compmax2 - prevcurdist);
            //cout << a << " a is splecial\n";
            mids.push_back(a);
        }
    }
    sort(mids.begin(), mids.end(), [](ll x, ll y){return x > y;});
    sort(diameters.begin(), diameters.end(), [](ll x, ll y){return x > y;});
    ll ans = diameters[0];
    ans = max(mids[0] + mids[1] + L , ans);
    ans = max(ans, mids[1] + mids[2] + 2 * L);
    //cout << ans;
    return ans;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 14936 KB Output is correct
2 Correct 31 ms 14940 KB Output is correct
3 Correct 21 ms 10844 KB Output is correct
4 Correct 6 ms 4444 KB Output is correct
5 Correct 5 ms 3676 KB Output is correct
6 Correct 8 ms 5468 KB Output is correct
7 Incorrect 2 ms 2648 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 14936 KB Output is correct
2 Correct 31 ms 14940 KB Output is correct
3 Correct 21 ms 10844 KB Output is correct
4 Correct 6 ms 4444 KB Output is correct
5 Correct 5 ms 3676 KB Output is correct
6 Correct 8 ms 5468 KB Output is correct
7 Incorrect 2 ms 2648 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 8912 KB Output is correct
2 Correct 16 ms 8912 KB Output is correct
3 Correct 16 ms 8912 KB Output is correct
4 Correct 21 ms 8932 KB Output is correct
5 Correct 18 ms 8916 KB Output is correct
6 Correct 18 ms 9936 KB Output is correct
7 Correct 18 ms 9384 KB Output is correct
8 Correct 21 ms 8912 KB Output is correct
9 Correct 16 ms 8912 KB Output is correct
10 Correct 16 ms 9340 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 6 ms 6520 KB Output is correct
13 Correct 7 ms 7028 KB Output is correct
14 Correct 7 ms 6520 KB Output is correct
15 Correct 7 ms 6764 KB Output is correct
16 Correct 6 ms 6272 KB Output is correct
17 Correct 7 ms 5492 KB Output is correct
18 Correct 7 ms 7108 KB Output is correct
19 Correct 6 ms 6272 KB Output is correct
20 Incorrect 1 ms 2652 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 14936 KB Output is correct
2 Correct 31 ms 14940 KB Output is correct
3 Correct 21 ms 10844 KB Output is correct
4 Correct 6 ms 4444 KB Output is correct
5 Correct 5 ms 3676 KB Output is correct
6 Correct 8 ms 5468 KB Output is correct
7 Incorrect 2 ms 2648 KB Output isn't correct
8 Halted 0 ms 0 KB -