oj.uz

Submission #251170

# Submission time Handle Problem Language Result Execution time Memory
251170 2020-07-20T13:20:36 Z AaronNaidu Dreaming (IOI13_dreaming) C++14
0 / 100
 57 ms 12920 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

vector<pair<int, int>> graph[100001];
int dists[100001];
bool visited[100001];
int maxDist = 0;
int maxNode = 0;

void dfs(int node, int parent, int distance) {
    dists[node] = distance;
    if (dists[node] > maxDist)
    {
        maxDist = dists[node];
        maxNode = node;
    }
    for (auto i : graph[node])
    {
        if (i.first != parent)
        {
            dfs(i.first, node, distance + i.second);
        }
    }
    visited[node] = true;
}

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({b[i],t[i]});
        graph[b[i]].push_back({a[i], t[i]});
    }
    dfs(0, -1, 0);    
    //cout << "Done dfs1 landed on " << maxNode << "\n";
    int dfsFrom = maxNode;
    maxDist = 0;
    maxNode = dfsFrom;
    dfs(dfsFrom, -1, 0);
    //cout << "Done dfs2 landed on " << maxNode << "\n";
    int currDist = maxDist;
    int prevCurrDist = currDist;
    int currNode = maxNode;
    while (currDist > maxDist/2)
    {
        for (auto i : graph[currNode])
        {
            if (dists[i.first] < dists[currNode])
            {
                currNode = i.first;
                prevCurrDist = currDist;
                currDist = dists[currNode];
                break;
            }
        }
    }
    //cout << "Cand dists are " << currDist << " " << prevCurrDist << " out of " << maxDist << "\n";
    int ans1 = min(max(currDist, maxDist - currDist), max(prevCurrDist, maxDist - prevCurrDist));
    int start2 = 0;
    for (int i = 0; i < n; i++)
    {
        if (!visited[i])
        {
            //cout << "Starting from " << start2 << "\n";
            break;
        }
        start2++;
    }
    maxDist = 0;
    maxNode = start2;
    dfs(start2, -1, 0);
    //cout << "Done dfs3 landed on " << maxNode << "\n";
    dfsFrom = maxNode;
    maxDist = 0;
    maxNode = dfsFrom;
    dfs(dfsFrom, -1, 0);
    //cout << "Done dfs4 landed on " << maxNode << "\n";
    currDist = maxDist;
    prevCurrDist = currDist;
    currNode = maxNode;
    while (currDist > maxDist/2)
    {
        for (auto i : graph[currNode])
        {
            if (dists[i.first] < dists[currNode])
            {
                currNode = i.first;
                prevCurrDist = currDist;
                currDist = dists[currNode];
                break;
            }
        }
    }
    //cout << "Cand dists are " << currDist << " " << prevCurrDist << " out of " << maxDist << "\n";
    int ans2 = min(max(currDist, maxDist - currDist), max(prevCurrDist, maxDist - prevCurrDist));
    //cout << "Ans 1 is " << ans1 << "\n";
    //cout << "Ans 2 is " << ans2 << "\n";
    return ans1 + ans2 + l;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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