Submission #1078207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078207		clementine	Dreaming (IOI13_dreaming)	C++17	100 / 100	72 ms	17788 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll distances[100005], dist2[100005];
vector<pair<int , int>> graph[100005];
bool visited[100005], vis2[100005];
ll compmax = -1, compmax2 = -1;
int compmaxnode = -1, compmaxn2 = -1;
int parent[100005];
ll pardist[100005];
void dfs(int u)
{
    visited[u] = true;
    if(compmax < distances[u])
    {
        compmax = distances[u];
        compmaxnode = u;
    }
    for(auto v: graph[u])
    {
        if(!visited[v.second])
        {
            distances[v.second] = distances[u] + v.first;
            dfs(v.second);
        }
    }
}


void dfs2(int u)
{
    vis2[u] = true;
    //cout << u << "is here \n";
    if(compmax2 < dist2[u])
    {
        compmax2 = dist2[u];
        compmaxn2 = u;
    }
    for(auto v: graph[u])
    {
        //cout << v.second << " thought " <<  vis2[v.second] << '\n';
        if(!vis2[v.second])
        {
            parent[v.second] = u;
            pardist[v.second] = v.first;
            dist2[v.second] = dist2[u] + v.first;
            dfs2(v.second);
        }
    }
}

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({T[i], B[i]});
        graph[B[i]].push_back({T[i], A[i]});
    }
    vector<ll> mids, diameters;
    for(int i = 0; i < N; i ++)
    {
        if(!visited[i])
        {
            //cout << i <<" this is i \n";
            compmax = -1, compmaxnode = -1;
            compmax2 = -1, compmaxn2 = -1;
            dfs(i);
            //cout << compmaxnode << " s \n";
            parent[compmaxnode] = -1;
            dfs2(compmaxnode);
            //cout << compmaxn2 << " e \n";
            diameters.push_back(compmax2);
            ll curdist = 0, prevcurdist = 0;
            while(compmax2 - curdist > curdist)
            {
                prevcurdist = curdist;
                curdist += pardist[compmaxn2];
                compmaxn2 = parent[compmaxn2];
                //cout << curdist << " also " << compmaxn2 << '\n';
            }
            ll a ;
            if(compmax - curdist == curdist)
            {
                a = curdist;
            }
            else 
                a = min(curdist, compmax2 - prevcurdist);
            //cout << a << " a is splecial\n";
            mids.push_back(a);
        }
    }
    sort(mids.begin(), mids.end(), [](ll x, ll y){return x > y;});
    sort(diameters.begin(), diameters.end(), [](ll x, ll y){return x > y;});
    ll ans = diameters[0];
    if(mids.size() >= 2)
        ans = max(mids[0] + mids[1] + L , ans);
    if(mids.size() >= 3)
        ans = max(ans, mids[1] + mids[2] + (2 * L));
    //cout << ans;
    return ans;
}

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