Submission #1180870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180870		countless	Dreaming (IOI13_dreaming)	C++20	100 / 100	93 ms	52516 KiB

dreaming

//i'm gnona explode

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>

#include "dreaming.h"

/*
Global:

• PARENTS = vect. keeps track of parents
• COLORS =  vect. keeps of visited nodes
• DIST = (vect of pair<int, int>). NODE X -> DISTANCE TO ROOT
• ADJ = (vect of v<pair<int,int>>). adjacency list of the OG graph
• max_distance = ll. used to identify tree diameter
• ending_vertex = int. NODE WHERE DFS ENDS

*/
using namespace std;

using ll = long long int;

vector<bool> vis(1e6 + 5, false);
vector<int> parents(1e6 + 5, -1);
vector<int> colors(1e6 + 5, 0);
vector<pair<int, int> > dist(1e6+5);
vector<vector<pair<int, int>>> adj(1e6+100);
int max_distance = -1;
int ending_vertex = -1;


void printDist(int n) {
    for (int i = 0; i < n; i++) {
        cout << "Vertex " << i << ": Distance = " << dist[i].first << endl;
    }
}

void dfs(int vertex, int parent, int id){

    //cout << "ITERATION: " << vertex << "\n";
    //printDist(5);
    //cout << "\n";

    // colors[vertex] = id;
    if (id == 2)
        vis[vertex] = true;

    if(dist[vertex].first >= max_distance){
        max_distance = dist[vertex].first;
        ending_vertex = vertex;
    }

    for(auto neighbour: adj[vertex]){
        int next_vertex = neighbour.first;
        int travel_time = neighbour.second;

        if (next_vertex == parent)
            continue;

        if (vis[next_vertex])
            continue;

        // if(colors[next_vertex] >= id){
        //     continue;
        // }

        // colors[next_vertex] = id;
        parents[next_vertex] = vertex;

        dist[next_vertex].first = dist[vertex].first + travel_time;
        
        //dist[next_vertex].first = dist[vertex].first + travel_time;
        dfs(next_vertex, vertex, id);
    }
}




int travelTime(int n, int m, int l, int A[], int B[], int T[]){

    for(int i = 0; i<m; i++){
        //converting everything to be a part of the adj data struct i know better
        int u = A[i];
        int v = B[i];
        int weight = T[i];

        pair<int, int> x;
        pair<int, int> y;
        x.first = v;
        x.second = weight;

        y.first = u;
        y.second = weight;
        adj[u].push_back(x);
        adj[v].push_back(y);
    }
    


    int R1 = -2e9+100;
    int R2 = -2e9+100;
    int R3 = -2e9+100;
    int D1 = -2e9+100;
    int radius = -1;

    vector<int> diameter;
    
    int cnt = 0;
    for(int i = 0; i<n; i++){
        //ITERATING THROUGHOUT EACH VERTEX INSIDE THE GRAPH
        if (vis[i])
            continue;

        // if (colors[i] >= 2){
        //     continue;
        // }
        cnt++;

        // colors[i] = 1;
        dfs(i, -1, 1);

        //printDist(n);
        //cout << "STARTS AT: " << ending_vertex << "\n"; 

        parents[ending_vertex] = -1;
        dist[ending_vertex].first = 0;
        max_distance = -1;

        // colors[i] = 2;
        dfs(ending_vertex, -1, 2);

        //cout << "\n------\n";

        //cout << "ENDS AT: " << ending_vertex << "\n";
        //printDist(n);

        diameter.clear();

        int p = ending_vertex;
        
        diameter.push_back(p);

        int sum_of_diameter = dist[ending_vertex].first;
        while(p != -1){
            diameter.push_back(parents[p]);
            p = parents[p];
        }

        
        //extra -1 woopsie
        diameter.pop_back();

        //reverse to go from the actual start to end order that i just like idk
        reverse(diameter.begin(), diameter.end());

        radius = sum_of_diameter;
        int d_size = diameter.size();

        if(d_size==0){
            ending_vertex = colors[i];
        }

        /*cout << "MAIN ROOT OF 2ND DFS: " << ending_vertex << "\n";
        cout << "SUM OF DIAMETER: " << sum_of_diameter << "\n";
        cout << "TREE DIAMETER\n";*/

        D1 = max(D1, sum_of_diameter);

        /*for(int j = 0; j<diameter.size(); j++){
            cout << diameter[j] << " ";
        }
        cout << "\n";*/

        for(int j=0; j<diameter.size(); j++){
            int index = diameter[j];
            //cout << "COMPARING: " << radius << " AND THE MAXIMUM OF " << dist[index].first << " " << sum_of_diameter - dist[index].first << "\n";
            radius = min(radius, max(dist[index].first, sum_of_diameter - dist[index].first));
        }

        //cout << "RADIUS: " <<  radius  << "\n";

        if(radius > R1){
            R3 = R2;
            R2 = R1;
            R1 = radius;
        }
        else if(radius > R2){
            R3 = R2;
            R2 = radius;
        }
        else if(radius > R3){
            R3 = radius;
        }

        //cout  << "\n~~~~\n";
    }

    /*cout << "TOP 3 MOST LARGEST OF RADII:\n";
    cout << R1 << " " << R2 << " " << R3 << "\n";*/
    cerr << cnt << endl;
    cerr << n-m << endl;
    if(n-m == 1){
        return D1;
    }
    else if(n-m == 2){
        return max(D1, R1+R2+l);
    }
    else{
        return max(D1, max(R1+R2+l, R2+R3+ (2*l)));
    }


    //return 0;
}


// int main(){
    
//     // n = # of vertices
//     // m = # of edges
//     // l = edge weight of new bridge
//     // A = 1st endpoint
//     // B = 2nd endpoint
//     // T = 1st and 2nd's edge weight
//     int n, m, l;
//     cin >> n >> m >> l;

//     int A[n];
//     int B[n];
//     int T[n];

//     for(int i =0; i<m; i++){
//         int x, y, z;
//         cin >> x >> y >> z;
//         A[i] = x;
//         B[i] = y;
//         T[i] = z;
//     }

//     cout << travelTime(n, m, l, A, B, T);
// }

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