Submission #1179957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179957		peej	Dreaming (IOI13_dreaming)	C++20	0 / 100	35 ms	21188 KiB

dreaming

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

using namespace std;

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

        TreeNode(int i) {
            id = i;
        }

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

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

    PathInfo(TreeNode* node) {
        lastNode = node;
    }
};

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 (int 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, int group) {
    root->group = group;

    PathInfo* ans = nullptr;

    for (pair<TreeNode*,int> 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> findConnectedComponents(int N) {
    int groupNum = 0;
    vector<ll> radii;
    for (int 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],groupNum);
            PathInfo* diameter = farthestNode(nullptr,farthest->lastNode,groupNum);

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

            radii.push_back(findRadius(diameter));
            groupNum++;
        }
    }

    return radii;
}

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 (int i = 0; i < N; i++) {
        TreeNode* thisNode = new TreeNode(i);
        nodes[i] = thisNode;
    }

    for (int 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 this connected component
    vector<ll> ccs = findConnectedComponents(N);
    sort(ccs.begin(),ccs.end());

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

    return max(ccs[ccs.size()-1]+ccs[ccs.size()-2]+L, ccs[ccs.size()-2]+ccs[ccs.size()-3]+2*L);
}

//int main() {
//    int n,m,l; cin >> n >> m >> l;
//    int a[m],b[m],t[m];
//    for (int i = 0; i < m; i++) {
//        cin >> a[i] >> b[i] >> t[i];
//    }
//    cout << travelTime(n,m,l,a,b,t);
//}

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