oj.uz

Submission #676926

# Submission time Handle Problem Language Result Execution time Memory
676926 2023-01-01T16:04:13 Z fatemetmhr Amusement Park (JOI17_amusement_park) C++17
0 / 100
 30 ms 13776 KB 
// ~ 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;
}

// ~ 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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10264 KB Output is correct
2 Incorrect 5 ms 10256 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 13712 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10204 KB Output is correct
2 Correct 5 ms 10256 KB Output is correct
3 Incorrect 5 ms 10256 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 13724 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 13776 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -