Submission #1183992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183992		TroySer	꿈 (IOI13_dreaming)	C++20	100 / 100	151 ms	23376 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<vector<pair<ll, ll> > > adjList;
vector<bool> visited;

vector<bool> visitedDiameter;

pair<ll, ll> dfs1(ll u) {

    queue<pair<ll, ll> > q;
    q.push({u, 0LL});

    ll maxDist = 0, maxDistNode = u;

    while (!q.empty()) {

        auto &[currNode, currDist] = q.front();
        q.pop();

        visited[currNode] = true;
        visitedDiameter[currNode] = true;
        
        if (maxDist < currDist) {
            maxDist = currDist, maxDistNode = currNode;
        }

        for (auto &[v, w]: adjList[currNode]) {
            if (visitedDiameter[v]) continue;
            q.push({v, w + currDist});
        }

    }

    return {maxDist, maxDistNode};
    
}

bool foundPath = false;
vector<ll> thePathFound;

void getCompletePath(ll u, ll finish, vector<ll> &path) {

    visitedDiameter[u] = true;

    if (foundPath) return;
    if (u == finish) {
        thePathFound = path;
        foundPath = true;
        return;
    }

    for (auto &[v, w]: adjList[u]) {
        if (visitedDiameter[v]) continue;
        path.push_back(v);
        getCompletePath(v, finish, path);
        path.pop_back();
    }

}

map<pair<ll, ll>, ll> edgeWeights;

pair<ll, ll> getCR(ll startingNode) {

    ll N = adjList.size();

    visitedDiameter.clear();
    visitedDiameter.resize(N, false);
    ll farthestNode = dfs1(startingNode).second;

    visitedDiameter.clear();
    visitedDiameter.resize(N, false);
    auto [distFromOtherEnd, otherEndOfDiameter] = dfs1(farthestNode);

    foundPath = false;
    visitedDiameter.clear();
    visitedDiameter.resize(N, false);
    vector<ll> p;
    p.push_back(farthestNode);
    getCompletePath(farthestNode, otherEndOfDiameter, p);

    // cout << "path: ";
    // for (auto l: thePathFound) {
    //     cout << l << ", ";
    // }
    // cout << " (" << distFromOtherEnd << ")" << endl;

    ll bestCenterDist = distFromOtherEnd, bestCenter = farthestNode;

    ll oneEnd = 0, otherEnd = distFromOtherEnd;

    for (ll i = 0; i < thePathFound.size() - 1; i++) {
        ll currEdgeWeight = edgeWeights[make_pair(min(thePathFound[i], thePathFound[i + 1]), max(thePathFound[i], thePathFound[i + 1]))];
        oneEnd += currEdgeWeight;
        otherEnd -= currEdgeWeight;
        if (bestCenterDist > max(oneEnd, otherEnd)) {
            bestCenterDist = max(oneEnd, otherEnd);
            bestCenter = thePathFound[i + 1];
        }
    }

    return {bestCenter, bestCenterDist};

}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    
    adjList.clear();
    adjList.resize(N);

    visited.clear();
    visited.resize(N, false);

    for (ll i = 0; i < M; i++) {
        adjList[A[i]].push_back({B[i], T[i]});
        adjList[B[i]].push_back({A[i], T[i]});
        edgeWeights[make_pair(min(A[i], B[i]), max(A[i], B[i]))] = T[i];
    }


    // Find all the centers and radii of the islands

    vector<pair<ll, ll> > centerAndRadius;

    for (ll i = 0; i < N; i++) {
        if (!visited[i]) {
            auto [currCenter, currRadius] = getCR(i);
            centerAndRadius.push_back({currRadius, currCenter});
        }
    }


    // connect all of them as a star graph
    sort(centerAndRadius.begin(), centerAndRadius.end());
    for (ll i = 0; i < centerAndRadius.size() - 1; i++) {
        adjList[centerAndRadius[i].second].push_back({centerAndRadius[centerAndRadius.size() - 1].second, L});
        adjList[centerAndRadius[centerAndRadius.size() - 1].second].push_back({centerAndRadius[i].second, L});
    }

    // get longest path again
    visitedDiameter.clear();
    visitedDiameter.resize(N, false);
    ll farthestNode = dfs1(0).second;

    visitedDiameter.clear();
    visitedDiameter.resize(N, false);
    auto [distFromOtherEnd, otherEndOfDiameter] = dfs1(farthestNode);

    return distFromOtherEnd;

}

// const ll MAX_N = 1e5;

// static int A[MAX_N];
// static int B[MAX_N];
// static int T[MAX_N];

// int main() {
// 	int N, M, L, i;

// 	cin >> N >> M >> L;
// 	for (i = 0; i < M; i++)
// 		cin >> A[i] >> B[i] >> T[i];

// 	int answer = travelTime(N, M, L, A, B, T);
// 	printf("%d\n", answer);

// 	return 0;
// }

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