Submission #1179998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179998		peej	Dreaming (IOI13_dreaming)	C++20	100 / 100	75 ms	23992 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long int 
#define endl '\n'

using namespace std;

// i sincerely apologize to anyone looking at this code. This is the result of being under the influence of pickup coffee

class TreeNode {
    public:
        ll id;
        ll group = -1;
        vector<pair<TreeNode*, ll>> neighbors = vector<pair<TreeNode*,ll>>();

        TreeNode(ll i) {
            id = i;
        }

        void addNeighbor(TreeNode* node, ll l) {
            neighbors.push_back(make_pair(node,l));
        }
};

struct PathInfo {
    vector<ll> path = vector<ll>();
    TreeNode* lastNode;
    ll length = 0;

    PathInfo(TreeNode* node) {
        lastNode = node;
        path.push_back(0);
    }
};

vector<TreeNode*> nodes;

ll findRadius(PathInfo* pathInfo) {
    if (pathInfo->path.size() == 0) return 0;
    if (pathInfo->path.size() == 1) return pathInfo->path[0];
    // get the radius by going like
    ll runningLength = 0;
    ll maxLength = pathInfo->path[pathInfo->path.size()-1];

    for (ll i = 1; i < pathInfo->path.size(); i++) {
        if (pathInfo->path[i] >= maxLength-(pathInfo->path[i])) {
            return min(pathInfo->path[i], maxLength-(pathInfo->path[i-1]));
        }
    }

    return 0;
}

// byproduct is that the group is labeled
PathInfo* farthestNode(TreeNode* parent, TreeNode* root, ll group) {
    root->group = group;

    PathInfo* ans = nullptr;

    for (pair<TreeNode*,ll> neighbor : root->neighbors) {
        if (parent != nullptr && neighbor.first->id == parent->id) continue;

        PathInfo* farthest = farthestNode(root, neighbor.first, group);
        farthest->length += neighbor.second;
        farthest->path.push_back(farthest->length);

        if (ans == nullptr || ans->length < farthest->length) {
            ans = farthest;
        }
    }

    if (ans == nullptr) {
        return new PathInfo(root);
    } else {
        return ans;
    }
}

vector<ll> radii, diameters;
ll numComponents = 0;

void findConnectedComponents(ll N) {
    for (ll i = 0; i < N; i++) {
        if (nodes[i]->group == -1) {
            // dfs w that as a root node, then do stuff
            // get tha radius GRAAAAH
            PathInfo* farthest = farthestNode(nullptr,nodes[i],numComponents);
            PathInfo* diameter = farthestNode(nullptr,farthest->lastNode,numComponents);

//            cout << "diameter of " << i << endl;
//            for (ll length : diameter->path) {
//                cout << length << " ";
//            }
//            cout << endl;

            radii.push_back(findRadius(diameter));
            diameters.push_back(diameter->length);
            numComponents++;
        }
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    nodes = vector<TreeNode*>(N);

    // make a node for each thing from 1-N
    for (ll i = 0; i < N; i++) {
        TreeNode* thisNode = new TreeNode(i);
        nodes[i] = thisNode;
    }

    for (ll i = 0; i < M; i++) {
        // a[i] is now a neighbor of b[i]
        nodes[A[i]]->addNeighbor(nodes[B[i]], T[i]);
        nodes[B[i]]->addNeighbor(nodes[A[i]], T[i]);
        // opposite too
    }

    // ok now dfs to get the radius of each connected component
    findConnectedComponents(N);
    sort(radii.begin(),radii.end());
    sort(diameters.begin(),diameters.end());

//    for (ll cc : radii) {
//        cout << cc << " ";
//    }
//    cout << endl;

    if (radii.size() >= 3) {
        return max(radii[numComponents-1]+radii[numComponents-2]+L, max(radii[numComponents-2]+radii[numComponents-3]+2*L, diameters[numComponents-1]));
    } else if (radii.size() == 2) {
        return max(radii[0] + radii[1] + L, diameters[1]);
    } else {
        return diameters[0];
    }
}

//ll main() {
//    ll n,m,l; cin >> n >> m >> l;
//    ll a[m],b[m],t[m];
//    for (ll i = 0; i < m; i++) {
//        cin >> a[i] >> b[i] >> t[i];
//    }
//    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