oj.uz

Submission #590974

# Submission time Handle Problem Language Result Execution time Memory
590974 2022-07-06T16:17:41 Z KrisjanisP Dreaming (IOI13_dreaming) C++17
0 / 100
 218 ms 26900 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<ll,ll>;
const ll MX = 100000;
vector<ii> AL[MX];
bool visited[MX];

map<ii,ll> maxDepthMem;
// returns the maximum depth
ll maxDepth(ll v, ll p)
{
    if(maxDepthMem.count({v,p}))
        return maxDepthMem[{v,p}];
    ll res = 0;
    for(auto& [u,w]: AL[v])
    {
        if(u==p) continue;
        res = max(res, maxDepth(u,v)+w);
    }
    maxDepthMem[{v,p}] = res;
    return res;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(ll i=0;i<M;i++)
    {
        ll a = A[i], b=B[i], w=T[i];
        AL[a].push_back({b,w});
        AL[b].push_back({a,w});
    }
    vector<ll> ecc; // eccentricity vector
    for(ll i=0;i<N;i++)
    {
        if(visited[i]) continue;
        vector<ll> nodes;
        queue<ll> q;
        q.push(i);
        visited[i]=1;
        nodes.push_back(i);
        while(!q.empty())
        {
            ll v = q.front(); q.pop();
            for(auto& [u,w]: AL[v])
            {
                if(visited[u]) continue;
                q.push(u);
                visited[u]=1;
                nodes.push_back(u);
            }
        }
        //cout<<"nodes: "; for(ll v: nodes) cout<<v<<" "; cout<<"\n";
        ll mnMxDepth = 1e9;
        for(ll v: nodes)
        {
            ll mxDepth = 0;
            for(auto& [u,w]: AL[v])
                mxDepth=max(mxDepth, maxDepth(u,v)+w);
            mnMxDepth = min(mnMxDepth, mxDepth);
        }
        ecc.push_back(mnMxDepth);
    }
    //cout<<"ecc: "; for(ll x: ecc) cout<<x<<" "; cout<<"\n";
    sort(ecc.begin(),ecc.end(),greater<ll>());
    if(ecc.size()==1) return ecc[0];
    else return ecc[0]+ecc[1]+L;
}

Subtask #1
0 / 14.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 9796 KB Output is correct
2 Incorrect 49 ms 9940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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