제출 #1309387

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309387		marcogambaro	Telepathy (JOI25_telepathy)	C++20	0 / 100	4 ms	816 KiB

telepathy

#include "telepathy.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> G;
vector<int> P;
int d1, d2;

void read(int N, vector<int> &a, vector<int> &b) {
    for(int i=0; i<N-1; i++) {
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }
}

void findd(int N) {
    vector<int> dg(N);
    for(int i=0; i<N; i++) dg[i] = G[i].size();

    queue<int> q;
    vector<int> dp(N);
    int r = N;
    for(int i=0; i<N; i++) if(dg[i] == 1) q.push(i), dp[i] = 1;
    int M = 1;

    while(!q.empty()) {
        int n = q.front();
        q.pop();
        r--;

        for(int n2: G[n]) {
            if(--dg[n2] == 1) {
                q.push(n2);
                dp[n2] = dp[n]+1;
                M = max(M, dp[n2]);
            }
        }
    }

    for(int i=0; i<N; i++) {
        if(dp[i] == M) {
            if(d1 == -1) d1 = i;
            else         d2 = i;
        }
    }

    P.resize(N);
    auto dfs = [&](int n, int from, auto &&dfs) -> void {
        if(n == -1)return;
        for(int n2: G[n]) {
            if(n2 == from) continue;
            P[n2] = n;
            dfs(n2, n, dfs);
        }
    };
    dfs(d1, d2, dfs);
    dfs(d2, d1, dfs);
    P[d1] = d1;
    if(d2 != -1) P[d2] = d2;
}


std::vector<int> Aitana(int N, std::vector<int> A, std::vector<int> B, int S, int subtask) {
    G = vector(N, vector<int>());
    read(N, A, B);
    findd(N);
    
    vector<int> opp = {3, -2, 0, 11, 37, -23, 0, 20};
    stack<int> st;
    vector<int> ans = {S};
    int n = S;

    for(int i=0; i<opp.size() && n != d1 && n != d2; i++) {
        int x = opp[i];
        if(x > 0) {
            for(int j=0; j<x; j++) {
                ans.push_back(P[n]);
                st.push(n);
                n = P[n];
            }
        }
        else if(x < 0) {
            for(int j=0; j<-x; j++) {
                ans.push_back(st.top());
                n = st.top();
                st.pop();
            }
        } 
        else {
            i++;
            x = opp[i];
            for(int j=0; j<x; j++) ans.push_back(n);
        }
    }

    while(n != d1 && n != d2) {
        ans.push_back(P[n]);
        n = P[n];
    }

    while(ans.size() <= 10*N) {
        ans.push_back(n);
    }

    return ans;
}

std::vector<int> Bruno(int N, std::vector<int> C, std::vector<int> D, int T, int subtask) {
    G = vector(N, vector<int>());
    read(N, C, D);
    findd(N);

    vector<int> opp = {0, 2, 13, -8, 0, 29, 43};
    stack<int> st;
    vector<int> ans = {T};
    int n = T;

    for(int i=0; i<opp.size() && n != d1 && n != d2; i++) {
        int x = opp[i];
        if(x > 0) {
            for(int j=0; j<x; j++) {
                ans.push_back(P[n]);
                st.push(n);
                n = P[n];
            }
        }
        else if(x < 0) {
            for(int j=0; j<-x; j++) {
                ans.push_back(st.top());
                n = st.top();
                st.pop();
            }
        } 
        else {
            i++;
            x = opp[i];
            for(int j=0; j<x; j++) ans.push_back(n);
        }
    }

    while(n != d1 && n != d2) {
        ans.push_back(P[n]);
        n = P[n];
    }

    while(ans.size() <= 10*N) {
        if(d2 == -1 || n == d2) {
            ans.push_back(d1);
            n = d1;
        }
        else {
            ans.push_back(d2);
            n = d2;
        }
    }

    return ans;
}

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