Submission #1370710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370710		TroySer	Telepathy (JOI25_telepathy)	C++20	0 / 100	2082 ms	824 KiB

telepathy

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

using namespace std;
using ll = int;

const ll INF = 1e18;

vector<int> Aitana(int N, vector<int> A, vector<int> B, int S, int subtask) {
    
    vector<vector<ll> > adjMat(N, vector<ll>(N, INF));
    for (ll i = 0; i < N - 1; i++) {
        adjMat[A[i]][B[i]] = adjMat[B[i]][A[i]] = 1;
    }

    for (ll k = 0; k < N; k++) {
        for (ll i = 0; i < N; i++) {
            for (ll j = 0; j < N; j++) {
                adjMat[i][j] = min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]);
            }
        }
    }

    ll hasMnDist = -1;
    ll mnDistSoFar = INF;

    for (ll i = 0; i < N; i++) {
        ll mxDist = 0;
        for (ll j = 0; j < N; j++) {
            mxDist = max(mxDist, adjMat[i][j]);
        }
        if (mxDist < mnDistSoFar) {
            mnDistSoFar = mxDist;
            hasMnDist = i;
        }
    }

    ll currNode = S;
    ll currDist = adjMat[currNode][hasMnDist];

    vector<ll> currPath;
    currPath.push_back(currNode);

    while (currNode != hasMnDist) {
        for (ll i = 0; i < N; i++) {
            if (adjMat[currNode][i] == currDist - 1) {
                currNode = i; 
                currDist--;
                currPath.push_back(i);
                break;
            }
        }
    }

    while (currPath.size() < 10*N) {
        currPath.push_back(hasMnDist);
    }

    return currPath;

}

vector<int> Bruno(int N, vector<int> C, vector<int> D, int T, int subtask) {
    
    vector<vector<ll> > adjMat(N, vector<ll>(N, INF));
    for (ll i = 0; i < N - 1; i++) {
        adjMat[C[i]][D[i]] = adjMat[D[i]][C[i]] = 1;
    }

    for (ll k = 0; k < N; k++) {
        for (ll i = 0; i < N; i++) {
            for (ll j = 0; j < N; j++) {
                adjMat[i][j] = min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]);
            }
        }
    }

    ll hasMnDist = -1;
    ll mnDistSoFar = INF;

    for (ll i = 0; i < N; i++) {
        ll mxDist = 0;
        for (ll j = 0; j < N; j++) {
            mxDist = max(mxDist, adjMat[i][j]);
        }
        if (mxDist < mnDistSoFar) {
            mnDistSoFar = mxDist;
            hasMnDist = i;
        }
    }

    ll currNode = T;
    ll currDist = adjMat[currNode][hasMnDist];

    vector<ll> currPath;
    currPath.push_back(currNode);

    while (currNode != hasMnDist) {
        for (ll i = 0; i < N; i++) {
            if (adjMat[currNode][i] == currDist - 1) {
                currNode = i; 
                currDist--;
                currPath.push_back(i);
                break;
            }
        }
    }

    while (currPath.size() < 10*N) {
        currPath.push_back(hasMnDist);
    }

    return currPath;

}

Compilation message (stderr)

telepathy.cpp:7:16: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
    7 | const ll INF = 1e18;
      |                ^~~~

• Subtask 1: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20