Submission #1166636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166636		lampooppp	Amusement Park (JOI17_amusement_park)	C++20	83 / 100	17 ms	2888 KiB

Joi

//#ifndef rtgsp
#include "Joi.h"
//#endif // rtgsp


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


const int N=10000;
vector<int> adj[N+1];
vector<int> treeadj[N+1];
int h[N+1];
int mx[N+1];
int pa[N+1];
int id[N+1];

void MessageBoard(int attr, int msg);


void dfs(int u)
{
    mx[u]=h[u];
    for(int v : adj[u])
    {
        if(h[v]) continue;
        h[v]=h[u]+1;
        pa[v]=u;
        treeadj[u].push_back(v);
       // treeadj[v].push_back(u);
        dfs(v);
        mx[u]=max(mx[u],mx[v]);
    }
}
int dem=0;

void traverse(int u, long long X)
{
    MessageBoard(u,(X>>dem)&1);
    id[u]=dem++;
    if(dem==60) return;
    for(int v : treeadj[u])
    {
        traverse(v,X);
        if(dem==60) return ;
    }
}


void Joi(int N, int M, int A[], int B[], long long X, int T)
{
    for(int i=0;i<N;++i)
    {
        adj[i].clear();
        treeadj[i].clear();
    }
    for(int i=0;i<M;++i)
    {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    h[0]=1;
    dfs(0);
    if(mx[0]>=60)
    {
        for(int i=0;i<N;++i)
        {
            int x = (h[i]-1)%60;
            MessageBoard(i,(X>>x)&1);
        }
    }
    else
    {
        for(int i=0;i<N;++i)
        {
            sort(treeadj[i].begin(), treeadj[i].end(), [](int a, int b)
                 {
                     if(mx[a]==mx[b]) return a>b;
                     return mx[a]>mx[b];
                 });
        }
        dem=0;
        fill(id,id+N,-1);
        traverse(0,X);
        for(int i=0;i<N;++i)
        {
            if(id[i]==-1) MessageBoard(i,0);
        }
    }
}

Ioi

//#ifndef rtgsp
#include "Ioi.h"
//#endif // rtgsp


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


const int N=10000;
vector<int> adi2[N+1];
vector<int> treeadi2[N+1];
int h2[N+1];
int mx2[N+1];
int pa2[N+1];
int id2[N+1];

//void MessageBoard(int attr, int msg);
int Move(int dest);


void dfs2(int u)
{
    mx2[u]=h2[u];
    for(int v : adi2[u])
    {
        if(h2[v]) continue;
        h2[v]=h2[u]+1;
        pa2[v]=u;
        treeadi2[u].push_back(v);
       // treeadi2[v].push_back(u);
        dfs2(v);
        mx2[u]=max(mx2[u],mx2[v]);
    }
}
int dem22=0;
long long ans[N+1];

void traverse(int u)
{
    //MessageBoard(u,(X>>dem22)&1);
    id2[u]=dem22++;
    if(dem22==60) return;
    for(int v : treeadi2[u])
    {
        int x = Move(v);
        ans[dem22]=x;
        traverse(v);
        if(dem22==60) return ;
    }
    Move(pa2[u]);
}


long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
    for(int i=0;i<N;++i)
    {
        adi2[i].clear();
        treeadi2[i].clear();
    }
    for(int i=0;i<M;++i)
    {
        adi2[A[i]].push_back(B[i]);
        adi2[B[i]].push_back(A[i]);
    }
    h2[0]=1;
    dfs2(0);
    if(mx2[0]>=60)
    {
        if(h2[P]>=60)
        {
            int x = (h2[P]-1)%60;
            ans[x]=V;
            for(int i=1;i<=59;++i)
            {
                P=pa2[P];
                int x = (h2[P]-1)%60;
                ans[x]=Move(P);
            }
        }
        else
        {
            if(P==0) ans[0]=V;
            while(h2[P]!=1)
            {
                P=pa2[P];
                int x = Move(P);
                if(P==0) ans[0]=x;
            }

            for(int i=1;i<60;++i)
            {
                for(int v : treeadi2[P])
                {
                    if(mx2[v]>=60)
                    {
                        int x = Move(v);
                        ans[i]=x;
                        P=v;
                        break;
                    }
                }
            }
        }
    }
    else
    {
        if(P==0) ans[0]=V;
        while(h2[P]!=1)
        {
            P=pa2[P];
            int x = Move(P);
            if(P==0) ans[0]=x;
        }
        for(int i=0;i<N;++i)
        {
            sort(treeadi2[i].begin(), treeadi2[i].end(), [](int a, int b)
                 {
                     if(mx2[a]==mx2[b]) return a>b;
                     return mx2[a]>mx2[b];
                 });
        }
        dem22=0;
        traverse(0);
    }
    long long ret=0;
    for(long long i=0;i<60;++i)
    {
        ret+=(ans[i]<<i);
    }
    return ret;
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 0 / 17