Submission #1199169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199169		alexander707070	Amusement Park (JOI17_amusement_park)	C++20	100 / 100	57 ms	2376 KiB

Joi

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

#include "Joi.h"

namespace Alice{
    int n,m;
    vector<int> v[MAXN];

    const int bits=60;
    int bit[MAXN];

    bool vis[MAXN],trav[MAXN];
    vector<int> tree[MAXN],special;
    int topsort[MAXN],sz;
    int num;

    void dfs(int x,int p){
        trav[x]=true;

        if(num==bits)return;

        num++; vis[x]=true;
        special.push_back(x);
        bit[x]=num-1;

        if(p!=0){
            tree[p].push_back(x);
            tree[x].push_back(p);
        }

        for(int i:v[x]){
            if(trav[i])continue;
            dfs(i,x);
        }
    }

    void dfs2(int x,int p,int root){
        for(int i:tree[x]){
            if(i==p)continue;
            dfs2(i,x,root);
        }

        topsort[sz]=bit[x]; sz++;
    }

    void dfs3(int x,int p,int pos,int id){
        trav[x]=true;

        if(!vis[x]){
            bit[x]=topsort[pos%bits];
        }

        for(int i:v[x]){
            if(trav[i] or vis[i])continue;
            dfs3(i,x,pos+1,id);
        }
    }
};

void Joi(int N, int M, int A[], int B[], long long X, int T){
    using namespace Alice;

    n=N; m=M;

    for(int i=0;i<m;i++){
        A[i]++; B[i]++;
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
        A[i]--; B[i]--;
    }

    for(int i=1;i<=n;i++){
        sort(v[i].begin(),v[i].end());
    }

    dfs(1,0);
    
    for(int i:special){
        for(int f=1;f<=n;f++)trav[f]=false;
        
        sz=0;
        dfs2(i,0,i);

        dfs3(i,0,-1,i);
    }

    for(int i=0;i<n;i++){
        MessageBoard(i, ((1LL<<bit[i+1])&X) > 0 );
    }

    return;
}

Ioi

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

#include "Ioi.h"

namespace Bob{
    int n,m,parent[MAXN];
    vector<int> v[MAXN];

    const int bits=60;
    int bit[MAXN];

    bool vis[MAXN],trav[MAXN];
    vector<int> tree[MAXN],special;
    int topsort[MAXN],sz;
    int num;

    int sol[70];
    bool used[70];

    long long ans;

    void dfs(int x,int p){
        parent[x]=p; trav[x]=true;

        if(num<bits){
            num++; vis[x]=true;
            special.push_back(x);
            bit[x]=num-1;

            if(p!=0){
                tree[p].push_back(x);
                tree[x].push_back(p);
            }
        }

        for(int i:v[x]){
            if(trav[i])continue;
            dfs(i,x);
        }
    }

    void dfs2(int x,int p,int root){
        for(int i:tree[x]){
            if(i==p)continue;
            dfs2(i,x,root);
        }

        topsort[sz]=bit[x]; sz++;
    }

    void dfs3(int x,int p,int pos,int id){
        trav[x]=true;

        if(!vis[x]){
            bit[x]=topsort[pos%bits];
        }

        for(int i:v[x]){
            if(trav[i] or vis[i])continue;
            dfs3(i,x,pos+1,id);
        }
    }

    void dfs4(int x,int curr){
        used[bit[x]]=true;
        sol[bit[x]]=curr;

        for(int i:tree[x]){
            if(!used[bit[i]]){
                dfs4(i,Move(i-1));
                Move(x-1);
            }
        }
    }
};

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T){
    using namespace Bob;

    n=N; m=M;


    for(int i=0;i<m;i++){
        A[i]++; B[i]++;
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
        A[i]--; B[i]--;
    }

    for(int i=1;i<=n;i++){
        sort(v[i].begin(),v[i].end());
    }

    dfs(1,0);
    
    for(int i:special){
        for(int f=1;f<=n;f++)trav[f]=false;
        
        sz=0;
        dfs2(i,0,i);
        
        dfs3(i,0,-1,i);
    }


    P++; used[bit[P]]=true;
    sol[bit[P]]=V;

    for(int i=1;i<=bits-1 and !vis[P];i++){
        P=parent[P];
        V=Move(P-1);

        if(vis[P])break;

        used[bit[P]]=true;
        sol[bit[P]]=V;
    }

    if(vis[P]){
        dfs4(P,V);
    }
    
    for(int i=0;i<bits;i++){
        ans+=(long long) (1LL<<i) * sol[i];
    }

    return ans;
}

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