oj.uz

Submission #1078173

# Submission time Handle Problem Language Result Execution time Memory
1078173 2024-08-27T13:30:29 Z clementine Dreaming (IOI13_dreaming) C++17
0 / 100
 33 ms 16468 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])
        {
            //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";
            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);
            //cout << a << " a is splecial\n";
            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 33 ms 16468 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 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 33 ms 16468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8924 KB Output is correct
2 Correct 16 ms 8744 KB Output is correct
3 Correct 19 ms 8920 KB Output is correct
4 Correct 14 ms 8916 KB Output is correct
5 Correct 16 ms 8920 KB Output is correct
6 Correct 26 ms 9632 KB Output is correct
7 Correct 15 ms 9180 KB Output is correct
8 Correct 16 ms 8668 KB Output is correct
9 Correct 19 ms 8656 KB Output is correct
10 Correct 14 ms 8916 KB Output is correct
11 Correct 1 ms 2804 KB Output is correct
12 Correct 7 ms 5844 KB Output is correct
13 Correct 6 ms 6100 KB Output is correct
14 Correct 6 ms 5844 KB Output is correct
15 Correct 6 ms 5844 KB Output is correct
16 Correct 6 ms 5588 KB Output is correct
17 Correct 5 ms 4668 KB Output is correct
18 Correct 6 ms 6348 KB Output is correct
19 Correct 5 ms 5588 KB Output is correct
20 Incorrect 2 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 Incorrect 1 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 33 ms 16468 KB Output isn't correct
2 Halted 0 ms 0 KB -