Submission #591024

#	Time	Username	Problem	Language	Result	Execution time	Memory
591024		KrisjanisP	Dreaming (IOI13_dreaming)	C++14	100 / 100	774 ms	25568 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
using namespace std;
using ll = long long;
using ii = pair<ll,ll>;
const ll MX = 100000;
vector<pair<ii,ll>> AL[MX]; // {{u,w},e}
bool visited[MX];

bool maxDepthMemVis[2*MX];
ll maxDepthMem[2*MX];
ii edge[MX*2]; // directional {from, to}
// returns the maximum depth
ll maxDepth(ll e)
{
    if(maxDepthMemVis[e])
        return maxDepthMem[e];
    ll p = edge[e].first, v = edge[e].second;
    ll res = 0;
    for(auto& z: AL[v])
    {
        ll u = z.first.first;
        ll w = z.first.second;
        ll ne = z.second;
        if(u==p) continue;
        res = max(res, maxDepth(ne)+w);
    }
    maxDepthMemVis[e] = 1;
    maxDepthMem[e] = 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},2*i});
        AL[b].push_back({{a,w},2*i+1});
        edge[2*i] = {a,b};
        edge[2*i+1] = {b,a};
    }
    vector<ll> ecc; // eccentricity vector
    ll res = 0;
    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& z: AL[v])
            {
                ll u = z.first.first;
                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 = 1e10;
        for(ll v: nodes)
        {
            ll mxDepth = 0;
            for(auto& z: AL[v])
            {
                ll u = z.first.first;
                ll w = z.first.second;
                ll ne = z.second;
                mxDepth=max(mxDepth, maxDepth(ne)+w);
            }
            res = max(res,mxDepth);
            mnMxDepth = min(mnMxDepth, mxDepth);
        }
        ecc.push_back(mnMxDepth);
    }
    sort(ecc.begin(),ecc.end(),greater<ll>());
    //cout<<"ecc: "; for(ll x: ecc) cout<<x<<" "; cout<<"\n";
    res = max(res, ecc[0]);
    if(ecc.size()>=2) res=max(res,ecc[0]+ecc[1]+L);
    if(ecc.size()>=3) res=max(res,ecc[1]+ecc[2]+2*L);
    return res;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:73:20: warning: unused variable 'u' [-Wunused-variable]
   73 |                 ll u = z.first.first;
      |                    ^

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23