Submission #1184472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184472		droopy	Dreaming (IOI13_dreaming)	C++20	100 / 100	106 ms	43988 KiB

dreaming

// Jesu juva

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

#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vll vector<ll>
#define vull vector<ull>
#define vb vector<bool>
#define vpii vector<pii>
#define vvi vector<vi>
#define vvb vector<vb>
#define vvpii vector<vpii>
#define f(i,x,n) for(int i=x;i<n;i++)
#define fe(i,x,n) for(int i=x;i<=n;i++)

vb vis(1e6 + 5, false);
vi parent(1e6 + 5);
vi dist(1e6 + 5, INT_MAX);
vvpii adj(1e6 + 5,vpii());

int dep1,dep2;

void dfs(int root, bool mark) {
    vis[root] = mark;

    //* cout << "NODE " << root << " DIST " << dist[root] << endl;

    if (adj[root].size() == 1) {
        if (vis[adj[root][0].first]) {
            //* cout << "TRIGGA1" << endl;
            if (dist[root] > dist[dep2]) dep2 = root;
            return;
        }
        else if (dist[adj[root][0].first] != INT_MAX && !mark){
            //* cout << "TRIGGATOO" << endl;
            if (dist[root] > dist[dep1]) dep1 = root;
            return;
        }
    }

    for (auto &edge : adj[root]) {
        if ((dist[edge.first] != INT_MAX && !mark) || vis[edge.first]) continue;
        dist[edge.first] = dist[root] + edge.second;
        if (mark) parent[edge.first] = root;
        dfs(edge.first, mark);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    int d1=0,r1=0,r2=0,r3=0;

    f(i,0,M) {
        adj[A[i]].emplace_back(B[i],T[i]);
        adj[B[i]].emplace_back(A[i],T[i]);
    }

    /*f(i,0,N) {
        cout << "NODE " << i << endl;
        for (auto x: adj[i]) {
            cout << x.first << ' ' << x.second << endl;
        }
        cout << endl;
    }*/

    f(i,0,N) {
        if (vis[i]) continue;

        // found a new CC ITS A BLOODY TREEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
        // AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

        // find diameter endpoint 1
        dist[i] = 0;
        dep1 = i;
        //* cout << endl;
        dfs(i,false);
        //* if (dist[dep1] > 100) cout << "DEP1 " << dist[dep1] << endl;
        //* cout << "DEP1 " << dep1 << endl << endl;

        // find diameter endpoint 2
        parent[dep1] = -2;
        dep2 = dep1;
        dist[dep1] = 0;
        dfs(dep1,true);
        //* cout << "DEP2 " << dep2 << endl << endl;

        // check if diameter is the largest
        d1 = max(dist[dep2],d1);
        //* cout << "DIAMITTAH " << dist[dep2] << endl <<endl;

        // cut if only 1 connected component exists
        if (N-M==1) return d1;

        // go along diameter until we find the node that minimizes its distance with the farther diameter endpoint
        int radius = INT_MAX;
        {
            int u = dep2;
            //* if (dist[dep2] > 100) cout << "FINDING RADIUS " << dep2 << endl;
            while(u!=-2) {
                //if (dist[dep2] > 100) cout << u << endl;
                radius = min(radius, max(dist[u], dist[dep2] - dist[u]));
                u = parent[u];
                //*  cout <<u<<' '<<radius<<' '<<dist[u]<<' '<<dist[dep2]-dist[u]<< endl;
            }
        }

        //* cout << "RADIUS " << radius << endl << endl;

        // check if radius is in the top 3
        if (radius > r1) {
            r3 = r2;
            r2 = r1;
            r1 = radius;
        }
        else if (radius > r2) {
            r3 = r2;
            r2 = radius;
        }
        else if (radius > r3) {
            r3 = radius;
        }
        //cout << r1<<' '<<r2<<' '<<r3<<endl;
        // else useless cc
    }
    
    //* cout << "ANS " << d1 << ' ' << r1 << ' ' << r2 << ' ' << r3<< ' ' << L << endl;
    if (N-M==2) {
        return max(d1, r1+r2+L);
    }
    else {
        return max(d1, max(r1+L+r2, r2+L+L+r3));
    }
}
/*
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,l;
    cin >> n >> m >> l;
    int a[n],b[n],t[n];
    f(i,0,m) {
        cin >> a[i] >> b[i] >> t[i];
    }
    cout << travelTime(n,m,l,a,b,t) << endl;

}*/


// soli Deo gloria

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