제출 #1370718

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1370718		TroySer	Telepathy (JOI25_telepathy)	C++20	10 / 100	1336 ms	1200 KiB

telepathy

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

using namespace std;
using ll = int;

const ll INF = 1e9;

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 i = 0; i < N; i++) {
        adjMat[i][i] = 0;
    }

    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 (currDist > 0) {

        // cout << S << " " << currNode << " " << hasMnDist << endl;
        // cout << currDist << endl;

        for (ll i = 0; i < N; i++) {
            if (adjMat[currNode][i] > 1) continue;
            // cout << i << " " << adjMat[i][hasMnDist] << endl;
            if (adjMat[i][hasMnDist] == 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 i = 0; i < N; i++) {
        adjMat[i][i] = 0;
    }

    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 (currDist > 0) {

        // cout << S << " " << currNode << " " << hasMnDist << endl;
        // cout << currDist << endl;

        for (ll i = 0; i < N; i++) {
            if (adjMat[currNode][i] > 1) continue;
            // cout << i << " " << adjMat[i][hasMnDist] << endl;
            if (adjMat[i][hasMnDist] == currDist - 1) {
                currNode = i; 
                currDist--;
                currPath.push_back(i);
                break;
            }
        }
        
    }

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

    return currPath;

}

• 서브태스크 1: 10 / 40
• 서브태스크 2: 0 / 40
• 서브태스크 3: 0 / 20