Submission #1275298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275298		StefanSebez	Telepathy (JOI25_telepathy)	C++20	51 / 100	56 ms	904 KiB

telepathy

#include "telepathy.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=210,lg=8;
vector<int>E[N];
int par[N],sajz[N];
void DFS(int u,int p=-1){
    par[u]=p;sajz[u]=1;
    for(auto i:E[u]) if(i!=p) DFS(i,u),sajz[u]+=sajz[i];
}
vector<int> Solve(int n,vector<int>A,vector<int>B,int S,int bit){
    for(int i=0;i<=n;i++) E[i].clear();
    for(int i=0;i<n-1;i++){
        E[A[i]].pb(B[i]);
        E[B[i]].pb(A[i]);
    }
    DFS(0);
    vector<int>cent;
    for(int i=0;i<n;i++){
        bool moze=true;
        for(auto j:E[i]){
            if(j==par[i]) continue;
            if(2*sajz[j]>n) moze=false;
        }
        if(2*(n-sajz[i])>n) moze=false;
        if(moze) cent.pb(i);
    }
    DFS(cent[0]);
    vector<int>res={S},vtx;
    for(int u=S;u!=-1;u=par[u]) vtx.pb(u);
    if(cent.size()>=2&&(vtx.size()<=1||vtx[vtx.size()-2]!=cent[1])) vtx.pb(cent[1]);
    int m=vtx.size();
    for(int j=0,e=1,i=0;j<lg;j++,e<<=1){
        if(j%2==bit){
            for(int ct=0;ct<e;ct++){
                i++;if(i>=m) i=m-1;
                res.pb(vtx[i]);
            }
            for(int ct=0;ct<e;ct++) res.pb(vtx[i]);
        }
        else{
            for(int ct=0;ct<e;ct++) res.pb(vtx[i]);
            for(int ct=0;ct<e;ct++){
                i++;if(i>=m) i=m-1;
                res.pb(vtx[i]);
            }
        }
    }
    //for(auto i:res) printf("%i ",i);printf("\n");
    while(res.size()<10*n+1) res.pb(res.back());
    while(res.size()>10*n+1) res.pop_back();
    //for(auto i:res) printf("%i ",i);printf("\n");
    return res;
}
std::vector<int> Aitana(int n, std::vector<int> A, std::vector<int> B, int S, int subtask) {
    return Solve(n,A,B,S,0);
}

std::vector<int> Bruno(int n, std::vector<int> A, std::vector<int> B, int S, int subtask) {
    return Solve(n,A,B,S,1);
}

• Subtask 1: 20.4 / 40
• Subtask 2: 20.4 / 40
• Subtask 3: 10.2 / 20