Submission #1311952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311952		Faisal_Saqib	Telepathy (JOI25_telepathy)	C++20	10 / 100	52 ms	916 KiB

telepathy

// #include "telepathy.h"
#include<vector>
#include<iostream>
using namespace std;
// std::vector<int> Aitana(int N, std::vector<int> A, std::vector<int> B, int S,
//                         int subtask) {
//     vector<int> ans;
//     while(ans.size()<=10*N)
//     {
//         ans.push_back(ans.back());
//     }
//     return ans;
// }
const int TPL=500;
vector<int> ma[TPL],ord;
int h[TPL],par[TPL];
void dfs(int x,int p=-1)
{
    ord.push_back(x);
    par[x]=p;
    for(auto y:ma[x])
    {
        if(y!=p)
        {
            h[y]=h[x]+1;
            dfs(y,x);
            ord.push_back(x);
        }
    }
}
std::vector<int> Bruno(int N, std::vector<int> C, std::vector<int> D, int T,
                       int subtask) {
    for(int i=0;i<=N;i++)ma[i].clear();
    for(int i=0;i<N-1;i++)
    {
        ma[C[i]].push_back(D[i]);
        ma[D[i]].push_back(C[i]);
    }
    
    int xas=N/2,xas1=N/2;
    for(int i=0;i<N;i++)
    {
        if(ma[i].size()==1)
        {
            ord.clear();
            dfs(i);
            xas=ord[N/2];
            xas1=ord[(N-1)/2];
            break;
        }
    }
    ord.clear();
    h[xas]=1;
    dfs(xas); // only works for this P = Q shit subtask = 1
    vector<int> ans;
    ans.push_back(T);
    for(int i=1+((N+1)/2);i>=1;i--)
    {
        int sp=ans.size();
        while(h[T]>i){
            T=par[T];
            ans.push_back(T);
        }
        if(sp==ans.size())ans.push_back(T);
    }
    ans.push_back(xas1);
    while(ans.size()<=10*N)
    {
        ans.push_back(ans.back());
    }
    return ans;
}

std::vector<int> Aitana(int N, std::vector<int> C, std::vector<int> D, int T,
                       int subtask) {
    for(int i=0;i<=N;i++)ma[i].clear();
    for(int i=0;i<N-1;i++)
    {
        ma[C[i]].push_back(D[i]);
        ma[D[i]].push_back(C[i]);
    }
    int xas=N/2,xas1=N/2;
    for(int i=0;i<N;i++)
    {
        if(ma[i].size()==1)
        {
            ord.clear();
            dfs(i);
            xas=ord[N/2];
            xas1=ord[(N-1)/2];
            break;
        }
    }
    ord.clear();
    h[xas]=1;
    dfs(xas); // only works for this P = Q shit subtask = 1
    vector<int> ans;
    // cout<<"Aitana: ";
    ans.push_back(T);
    for(int i=1+((N+1)/2);i>=1;i--)
    {
        int sp=ans.size();
        while(h[T]>i){
            T=par[T];
            ans.push_back(T);
        }
        if(sp==ans.size())ans.push_back(T);
    }
    while(ans.size()<=10*N)
    {
        ans.push_back(ans.back());
    }
    return ans;
}

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