제출 #590975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
590975		KrisjanisP	꿈 (IOI13_dreaming)	C++17	18 / 100	198 ms	25712 KiB

dreaming

#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>());
    ll 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;
}

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