제출 #1309581

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309581		marcogambaro	Telepathy (JOI25_telepathy)	C++20	31 / 100	60 ms	896 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) {
    d1 = -1;
    d2 = -1;
    int M = 0;
    vector<int> d(N);
    vector<int> from(N);

    auto dfs = [&](int n, int f, auto &&dfs) -> void {
        if(n == -1) return;
        from[n] = f;
        for(int n2: G[n]) {
            if(n2 == f) continue;
            d[n2] = d[n]+1;
            if(d[n2] >= d[M])  M = n2;
            dfs(n2, n, dfs);
        }
    };

    dfs(0, -1, dfs);
    d[M] = 0;
    dfs(M, -1, dfs);

    d1 = M;
    for(int i=0; i<d[M]/2; i++) {
        d1 = from[d1];
    }
    if(d[M]%2) d2 = from[d1];

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

    fprintf(stderr, "d1 = %d   d2 = %d \n", d1, d2);
}

vector<int> solve1(int N, int x, bool type) {
    vector<int> ans = {x};
    vector<int> to(N);

    auto dfs = [&](int n, int from, auto &&dfs) -> bool {
        if(n == 0) return true;
        for(int n2: G[n]) {
            if(n2 == from) continue;
            if(dfs(n2, n, dfs)) {
                to[n] = n2;
                return 1;
            }
        }

        return 0;
    };

    while(ans.size() <= 10*N+1) {
        ans.push_back(x = to[x]);
    }
    return ans;
}


vector<int> opa = {3, 0, 2, -1, 3, 0, 2, -4, 9, 0, 1, 14, 0, 1, 6, -6, 0, 2, 1, 0, 1, 1, 0, 1, 1, 0, 7, -3, 0, 1, -1, 0, 1, -1, 0, 1, -9, 27};
vector<int> opb = {1, -1, 0, 1, 12, 0, 1, -5, 0, 2, -1, 1, 0, 3, 10, 0, 1, -1, 0, 1, -4, 0, 1, 24,0, 1, 1, 0, 1, 10, 0, 1, -25, 0, 1};



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);

    //if(subtask == 1) return solve1(N, S, 0);
    
    vector<int> opp;
    opp = opa;
    stack<int> st;
    vector<int> ans = {S};
    int n = S;

    P[d1] = d1;
    if(d2 != -1) P[d2] = d2;

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

    while(n != d1 && n != d2 && ans.size() <= 10*N) {
        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);

    //if(subtask == 1) return solve1(N, T, 1);

    vector<int> opp;
    opp = opb;
    stack<int> st;
    vector<int> ans = {T};
    int n = T;

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

    while(n != d1 && n != d2 && ans.size() <= 10*N) {
        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;
}

#ifdef MARCO
signed main() {
    int qq; cin >> qq; cin >> qq;
    int N; cin >> N;
    vector<int> a(N), b(N);
    for(int i=0; i<N-1; i++) {
        cin >> a[i] >> b[i];
    }

    vector<int> p(N), q(N);
    for(auto &i: p) cin >> i;
    for(auto &i: q) cin >> i;

    int A, B; cin >> A >> B;

    vector<int> AA = Aitana(N, a, b, A, 0);
    vector<int> BB = Bruno(N, a, b, B, 0);

    cout << "AA:\n";
    for(int i: AA) cout << i << " "; cout << "\n";

    cout << "BB:\n";
    for(int i: BB) cout << i << " "; cout << "\n";

    for(int i=0; i<10*N; i++) {
        if(AA[i] == BB[i]) {
            cout << "answer = " << i << "\n";
            return 0;
        }
    }
}
#endif

• Subtask 1: 10 / 40
• Subtask 2: 16.4 / 40
• Subtask 3: 5 / 20