Submission #676926

#	Time	Username	Problem	Language	Result	Execution time	Memory
676926		fatemetmhr	Amusement Park (JOI17_amusement_park)	C++17	0 / 100	30 ms	13776 KiB

Joi

// ~ Be Name Khoda ~

#include "Joi.h"
#include<bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn5 =  1e5   + 10;

static bool good[maxn5], mark[maxn5];
static int num = 0, bit[maxn5], root, h[maxn5], par[maxn5];
static vector <int> adj[maxn5], have[maxn5];

static void dfs(int v){
    mark[v] = true;
    num++;
    if(num <= 60){
        bit[v] = num - 1;
        good[v] = true;
    }
    for(auto u : adj[v]) if(!mark[u]){
        mark[u] = v;
        par[u] = v;
        dfs(u);
    }
}

static void dfs2(int v, int par){
    have[v].pb(bit[v]);
    for(auto u : adj[v]) if(u != par && good[u])
        dfs2(u, v);
}

static void dfs3(int v, int par){
    if(!good[v])
        bit[v] = have[root][int(have[root].size()) - (h[v] % int(have[root].size()))];
    for(auto u : adj[v]) if(u != par && !good[u]){
        h[u] = h[v] + 1;
        dfs3(u, v);
    }
}

void Joi(int n, int m, int A[], int B[], ll X, int T){
    for(int i = 0; i < m; i++){
        adj[A[i]].pb(B[i]);
        adj[B[i]].pb(A[i]);
    }
    par[0] = -1;
    dfs(0);
    for(int i = 0; i < n; i++)
        adj[i].clear();
    for(int i = 1; i < n; i++){
        adj[i].pb(par[i]);
        adj[par[i]].pb(i);
    }
    for(int i = 0; i < n; i++) if(good[i])
        dfs2(i, -1);
    for(int i = 0; i < n; i++) if(good[i]){
        root = i;
        dfs3(i, -1);
    }
    for(int i = 0; i < n; i++)
        MessageBoard(i, (X >> (bit[i])) & 1);
    return;
}

Ioi

// ~ Be Name Khoda ~

#include "Ioi.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn5 =  1e5   + 10;

static bool good[maxn5], mark[maxn5];
static int num = 0, bit[maxn5], done = 0, root;
static int par[maxn5], ans[maxn5], h[maxn5];
static vector <int> adj[maxn5], have[maxn5];
static ll x;

static void dfs(int v){
    mark[v] = true;
    num++;
    if(num <= 60){
        bit[v] = num - 1;
        good[v] = true;
    }
    for(auto u : adj[v]) if(!mark[u]){
        mark[u] = v;
        par[u] = v;
        dfs(u);
    }
}

static void dfs2(int v, int par){
    have[v].pb(bit[v]);
    for(auto u : adj[v]) if(u != par && good[u])
        dfs2(u, v);
}

static void dfs3(int v){
    if(!good[v])
        bit[v] = have[root][int(have[root].size()) - (h[v] % int(have[root].size()))];
    for(auto u : adj[v]) if(u != par[v] && !good[u]){
        h[u] = h[v] + 1;
        par[u] = v;
        dfs3(u);
    }
}

static void dfs4(int v){
    if(done == 60)
        return;
    done++;
    if(ans[v])
        x += (1LL << bit[v]);
    for(auto u : adj[v]) if(u != par[v] && good[u]){
        par[u] = v;
        ans[u] = Move(u);
        dfs4(u);
    }
    if(done < 60 && par[v] != -1)
        Move(par[v]);
}

ll Ioi(int n, int m, int A[], int B[], int p, int V, int T) {
    for(int i = 0; i < m; i++){
        adj[A[i]].pb(B[i]);
        adj[B[i]].pb(A[i]);
    }
    par[0] = -1;
    dfs(0);
    for(int i = 0; i < n; i++)
        adj[i].clear();
    for(int i = 1; i < n; i++){
        adj[i].pb(par[i]);
        adj[par[i]].pb(i);
    }
    for(int i = 0; i < n; i++) if(good[i])
        dfs2(i, -1);
    for(int i = 0; i < n; i++) if(good[i]){
        par[i] = -1;
        root = i;
        dfs3(i);
    }

    ans[p] = V;
    done = 0;
    while(!good[p] && done < 60){
        if(ans[p])
            x += (1LL << bit[p]);
        done++;
        p = par[p];
        ans[p] = Move(p);
    }
    if(done == 60)
        return x;
    par[p] = -1;
    dfs4(p);
    return x;
}

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