oj.uz

Submission #1078152

# Submission time Handle Problem Language Result Execution time Memory
1078152 2024-08-27T13:23:54 Z clementine Dreaming (IOI13_dreaming) C++17
0 / 100
 30 ms 16208 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);
        }
    }
}


void finddiameter()
{

}
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;
    for(int i = 0; i < N; i ++)
    {
        if(!visited[i])
        {
            compmax = -1, compmaxnode = -1;
            compmax2 = -1, compmaxn2 = -1;
            dfs(0);
            //cout << compmaxnode << '\n';
            parent[compmaxnode] = -1;
            dfs2(compmaxnode);
            //cout << compmaxn2 << '\n';
            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;
            }
            a = min(curdist, compmax2 - prevcurdist);
            mids.push_back(a);
        }
    }
    mids.push_back(0);
    sort(mids.begin(), mids.end(), [](ll x, ll y){return x > y;});
    ll ans = max(mids[0] + mids[1] + L , mids[1] + mids[2] + 2 * L);
    //cout << ans;
    return ans;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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