Submission #1222152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222152		MarwenElarbi	Amusement Park (JOI17_amusement_park)	C++20	0 / 100	18 ms	4936 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
//common
#define pb push_back
#define se second
#define fi first
const int nax=100005;
static vector<int> parent(nax);
static vector<int> tree[nax];
static int dp[nax];
static int special[nax];
static int dep[nax];
static vector<int> par(nax);
static int find(int x){
    if(x==parent[x]) return x;
    return parent[x]=find(parent[x]);
}
static bool sameset(int x,int y){
    return find(x)==find(y);
}
static void joinset(int x,int y){
    x=find(x);
    y=find(y);
    parent[x]=y;
}
static void dfs(int x,int p){
    dp[x]=1;
    par[x]=p;
    for(auto u:tree[x]){
        if(u==p) continue;
        dep[u]=dep[x]+1;
        dfs(u,x);
        if(special[u]) continue;
        dp[x]+=dp[u];
    }
    if(dp[x]>=60){
        special[x]=1;
    }
}

//1
static vector<int> cur;
static void traversal(int x){
    if(cur.size()>=60) return;
    cur.pb(x);
    for(auto u:tree[x]){
        if(u==par[x]) continue;
        if(special[u]) continue;
        traversal(u);
    }
}
static vector<int> paint(nax,0);
void Joi(int N, int M, int A[], int B[], long long X, int T){
    for (int i = 0; i < N; i++) parent[i]=i;
    for (int i = 0; i < M; ++i)
    {
        if(sameset(A[i],B[i])) continue;
        joinset(A[i],B[i]);
        tree[A[i]].pb(B[i]);
        tree[B[i]].pb(A[i]);
    }
    dfs(0,-1);
    if(!special[0]){
        pair<int,int> mn={nax,nax};
        for (int i = 0; i < N; ++i)
        {
            if(special[i]) mn=min(mn,make_pair(dep[i],i));
        }
        special[0]=1;
        special[mn.se]=0;
    }
    for (int i = 0; i < N; ++i)
    {
        if(special[i]) {
            cur.clear();
            traversal(i);
            for (int j = 0; j < 60; ++j)
            {
                if((1ll<<j)&X) paint[cur[j]]=1;
            }
        }
    }
    for (int i = 0; i < N; ++i)
    {
        if(paint[i]){
            MessageBoard(i,1);
        }else MessageBoard(i,0);
    }
    return;
}

Ioi

#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;
#define pb push_back
#define se second
#define fi first
const int nax=100005;
static vector<int> parent(nax);
static vector<int> tree[nax];
static int dp[nax];
static int special[nax];
static int dep[nax];
static vector<int> par(nax);
static int find(int x){
    if(x==parent[x]) return x;
    return parent[x]=find(parent[x]);
}
static bool sameset(int x,int y){
    return find(x)==find(y);
}
static void joinset(int x,int y){
    x=find(x);
    y=find(y);
    parent[x]=y;
}
static void dfs(int x,int p){
    dp[x]=1;
    par[x]=p;
    for(auto u:tree[x]){
        if(u==p) continue;
        dep[u]=dep[x]+1;
        dfs(u,x);
        if(special[u]) continue;
        dp[x]+=dp[u];
    }
    if(dp[x]>=60){
        special[x]=1;
    }
}
static vector<int> cte;
static void trav(int x){
    if(cte.size()>=60) return;
    for(auto u:tree[x]){
        if(cte.size()>=60) return;
        if(u==par[x]) continue;
        if(special[u]) continue;
        cte.pb(Move(u));
        trav(u);
        if(cte.size()>=60) return;
        Move(x);
    }
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T){
    for (int i = 0; i < N;++i)
    {
        parent[i]=i;
        tree[i].clear();
        dp[i]=0;
        special[i]=0;
    }
    for (int i = 0; i < M; ++i)
    {
        if(sameset(A[i],B[i])) continue;
        joinset(A[i],B[i]);
        tree[A[i]].pb(B[i]);
        tree[B[i]].pb(A[i]);
    }
    dfs(0,-1);

    if(!special[0]){
        pair<int,int> mn={nax,nax};
        for (int i = 0; i < N; ++i)
        {
            if(special[i]) mn=min(mn,make_pair(dep[i],i));
        }
        special[0]=1;
        special[mn.se]=0;
    }
    if(!special[P]){
        while(!special[par[P]]) {
            P=par[P];
            Move(P);
        }  
        cte.clear();
        cte.pb(Move(par[P]));
        P=par[P];
    }else cte.push_back(V);
    trav(P);
    long long ans=0;
    for (int i = 0; i < 60; ++i)
    {
        ans+=1ll*(cte[i]<<i); 
    }
    cte.clear();
    return ans;
}

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