oj.uz

Submission #648811

# Submission time Handle Problem Language Result Execution time Memory
648811 2022-10-08T11:01:45 Z LouayFarah Dreaming (IOI13_dreaming) C++14
0 / 100
 154 ms 26852 KB 
#include "bits/stdc++.h"
#include "dreaming.h"

using namespace std;

#define endl "\n"
#define ll long long int
#define pb push_back
#define mp make_pair
#define fi first
#define se second


const long long MOD = 1e9+7;
const long long INF = 1e18;

int nx[8] = {0, 0, -1, 1, 1, -1, 1, -1};
int ny[8] = {1, -1, 0, 0, -1, 1, 1, -1};

void dfs(vector<pair<ll, ll>> adj[], int u, vector<bool> &visited, vector<ll> &curr_comp)
{
    if(visited[u])
        return;
    visited[u] = true;
    curr_comp.pb(u);

    for(auto v: adj[u])
    {
        dfs(adj, v.fi, visited, curr_comp);
    }
}

void dfs_dist(vector<pair<ll, ll>> adj[], ll u, ll p, vector<int> &dist)
{
    for(auto v: adj[u])
    {
        if(v.fi!=p)
        {
            dist[v.fi] = dist[u] + v.se;
            dfs_dist(adj, v.fi, u, dist);
        }
    }
}

void bfs(vector<pair<ll, ll>> adj[], int b, int c, int N, vector<ll> &path)
{
    vector<bool> visited(N+1, false);
    queue<ll> q;
    vector<ll> parent(N+1, -1);

    visited[b] = true;
    q.push(b);

    while(!q.empty())
    {
        int x = q.front();
        q.pop();

        for(auto v: adj[x])
        {
            int y = v.fi;
            if(visited[y])
                continue;
            visited[y] = true;
            parent[y] = x;
        }
    }

    while(c!=-1)
    {
        path.pb(c);
        c = parent[c];
    }

    reverse(path.begin(), path.end());
}

int calculate_diameter(vector<pair<ll, ll>> adj[], int N, vector<ll> &path)
{
    int a = 1;
    vector<int> dist_a(N+1, 0);
    dfs_dist(adj, a, -1, dist_a);

    int b = -1;
    int maximum_a = 0;

    for(int i = 1; i<=N; i++)
    {
        if(dist_a[i]>maximum_a)
        {
            maximum_a = dist_a[i];
            b = i;
        }
    }

    vector<int> dist_b(N+1, 0);
    dfs_dist(adj, b, -1, dist_b);

    int c = -1;
    int maximum_b = 0;
    for(int i = 1; i<=N; i++)
    {
        if(dist_b[i]>maximum_b)
        {
            maximum_b = dist_b[i];
            c = i;
        }
    }

    bfs(adj, b, c, N, path);

    return dist_b[c];
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    //creating the graph
    vector<pair<ll, ll>> adj[N+1];
    for(int i = 0; i<M; i++)
    {
        adj[A[i]+1].pb(mp(B[i]+1, T[i]));
        adj[B[i]+1].pb(mp(A[i]+1, T[i]));
    }


    //extracting the 2 components
    vector<vector<ll>> comps;
    vector<bool> visited(N+1, false);
    for(int u = 1; u<=N; u++)
    {
        if(visited[u])
            continue;
        vector<ll> curr_comp;
        dfs(adj, u, visited, curr_comp);

        comps.pb(curr_comp);
    }


    //creating path1
    vector<ll> path1;
    int diameter1 = calculate_diameter(adj, N, path1);

    vector<int> dist1_left(N+1, 0), dist1_right(N+1, 0);
    dfs_dist(adj, path1[0], -1, dist1_left);
    dfs_dist(adj, path1[int(path1.size())-1], -1, dist1_right);

    int candidate1_1 = -1;
    int curr1 = diameter1;
    for(int i = 0; i<int(path1.size()); i++)
    {
        if(curr1<=diameter1/2)
        {
            candidate1_1 = path1[i];
            break;
        }
        curr1-=dist1_left[path1[i]];
    }

    int candidate2_1 = -1;
    curr1 = diameter1;
    for(int i = int(path1.size())-1; i>=0; i--)
    {
        if(curr1<=diameter1/2)
        {
            candidate2_1 = path1[i];
            break;
        }
        curr1-=dist1_right[path1[i]];
    }

    int node1 = -1;
    if(abs(diameter1/2-candidate1_1)<=abs(diameter1/2-candidate2_1))
    {
        node1 = candidate1_1;
    }
    else
    {
        node1 = candidate2_1;
    }

    if(node1==-1)
    {
        node1 = path1[0];
    }


    //creating path2
    vector<ll> path2;
    int diameter2 = calculate_diameter(adj, N, path2);

    vector<int> dist2_right(N+1, 0), dist2_left(N+1, 0);
    dfs_dist(adj, path2[0], -1, dist1_left);
    dfs_dist(adj, path2[int(path2.size())-1], -1, dist1_right);

    int candidate1_2 = -1;
    int curr2 = diameter2;
    for(int i = 0; i<int(path2.size()); i++)
    {
        if(curr2<=diameter2/2)
        {
            candidate1_2 = path2[i];
            break;
        }
        curr2-=dist2_left[path2[i]];
    }

    int candidate2_2 = -1;
    curr2 = diameter2;
    for(int i = int(path2.size())-1; i>=0; i--)
    {
        if(curr2<=diameter2/2)
        {
            candidate2_2 = path2[i];
            break;
        }
        curr2-=dist2_right[path2[i]];
    }

    int node2 = -1;
    if(abs(diameter2/2-candidate1_2)<=abs(diameter2/2-candidate2_2))
    {
        node2 = candidate1_2;
    }
    else
    {
        node2 = candidate2_2;
    }

    if(node2==-1)
    {
        node2 = path2[0];
    }

    //adding the edge

    adj[node1].pb(mp(node2, L));
    adj[node2].pb(mp(node1, L));

    vector<ll> temp;
    int res = calculate_diameter(adj, N, temp);

    return res;
}

Subtask #1
0 / 14.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

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

Subtask #6
0 / 23.0

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