Submission #828692

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
828692	2023-08-17T13:39:35 Z	GrindMachine	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	21 ms	7404 KB

// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "Joi.h"

static vector<int> adj[N];
static vector<int> cnt(N);
static vector<pii> group(N,{-1,-1});
static int ptr = 0;

static void build(int u){
    trav(v,adj[u]){
        if(group[v].ff != -1) conts;
        int id = group[u].ff;
        if(cnt[id] == 60){
            id = ptr++;
        }

        group[v] = {id,cnt[id]++};
        build(v);
    }
}

void Joi(int n, int m, int A[], int B[], long long X, int T) {
    rep(i,m){
        int u = A[i], v = B[i];
        adj[u].pb(v), adj[v].pb(u);
    }

    group[0] = {0,0};
    cnt[0]++;
    ptr++; 
    build(0);

    rep(i,n){
        int bit = group[i].ss;
        int b = 0;
        if(X & (1ll<<bit)) b = 1;
        MessageBoard(i,b);
    }
}

// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e4 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "Ioi.h"

static vector<int> adj[N];
static vector<int> cnt(N);
static vector<pii> group(N,{-1,-1});
static int ptr = 0;

static void build(int u){
    trav(v,adj[u]){
        if(group[v].ff != -1) conts;
        int id = group[u].ff;
        if(cnt[id] == 60){
            id = ptr++;
        }

        group[v] = {id,cnt[id]++};
        build(v);
    }
}

vector<int> adj2[60];
vector<bool> vis(60);
vector<int> actual_nodes(60);
vector<int> depth(60), deepest(60);
ll x_val = 0;

void dfs1(int u){
    vis[u] = 1;
    deepest[u] = depth[u];

    trav(v,adj2[u]){
        if(vis[v]) conts;
        depth[v] = depth[u]+1;
        dfs1(v);
        amax(deepest[u],deepest[v]);
    }
}

void dfs2(int u, int ret){
    vis[u] = 1;

    pii best = {-1,-1};
    trav(v,adj2[u]){
        if(vis[v]) conts;
        pii px = {deepest[v],v};
        amax(best,px);
    }

    trav(v,adj2[u]){
        if(vis[v]) conts;
        if(!ret and v == best.ss) conts;

        int b = Move(actual_nodes[v]);
        int bit = v;
        if(b) x_val |= (1ll<<bit);

        dfs2(v,1);

        Move(actual_nodes[u]);
    }

    if(!ret and best.ss != -1){
        int v = best.ss;

        int b = Move(actual_nodes[v]);
        int bit = v;
        if(b) x_val |= (1ll<<bit);

        dfs2(v,0);
    }
}

long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
    rep(i,m){
        int u = A[i], v = B[i];
        adj[u].pb(v), adj[v].pb(u);
    }

    group[0] = {0,0};
    cnt[0]++;
    ptr++; 
    build(0);

    // find closest good group
    queue<int> q2;
    vector<int> par(n,-1);
    q2.push(P);
    par[P] = P;

    int want = -1;

    while(!q2.empty()){
        int u = q2.front();
        q2.pop();
        int c = group[u].ff;
        if(cnt[c] == 60){
            want = u;
            break;
        }

        trav(v,adj[u]){
            if(par[v] == -1){
                q2.push(v);
                par[v] = u;
            }
        }
    }

    assert(want != -1);

    int root = group[want].ss;
    int root_val = V;

    vector<int> path;
    int o_want = want;

    while(want != P){
        path.pb(want);
        want = par[want];
    }

    reverse(all(path));

    trav(u,path){
        root_val = Move(u);
        P = u;
    }

    want = o_want;
    assert(P == want);

    int want_col = group[want].ff;

    rep(u,n){
        if(group[u].ff == want_col){
            actual_nodes[group[u].ss] = u;
        }
    }

    rep(u,n){
        trav(v,adj[u]){
            if(group[u].ff == want_col and group[v].ff == want_col){
                int x = group[u].ss;
                int y = group[v].ss;
                adj2[x].pb(y);
                adj2[y].pb(x);
            }
        }
    }

    if(root_val) x_val |= (1ll<<root);

    dfs1(root);
    fill(all(vis),0);
    dfs2(root,0);

    return x_val;
}

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4492 KB	Output is correct
2	Correct	2 ms	4512 KB	Output is correct
3	Correct	3 ms	4500 KB	Output is correct
4	Correct	2 ms	4500 KB	Output is correct
5	Correct	3 ms	4508 KB	Output is correct
6	Correct	2 ms	4504 KB	Output is correct
7	Correct	3 ms	4504 KB	Output is correct
8	Correct	2 ms	4504 KB	Output is correct
9	Correct	2 ms	4500 KB	Output is correct
10	Correct	2 ms	4496 KB	Output is correct
11	Correct	4 ms	4812 KB	Output is correct
12	Correct	2 ms	4496 KB	Output is correct
13	Correct	2 ms	4496 KB	Output is correct
14	Correct	3 ms	4580 KB	Output is correct
15	Correct	3 ms	4504 KB	Output is correct
16	Correct	3 ms	4508 KB	Output is correct
17	Correct	3 ms	4512 KB	Output is correct
18	Correct	3 ms	4580 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	7272 KB	Output is correct
2	Correct	18 ms	7348 KB	Output is correct
3	Correct	18 ms	7404 KB	Output is correct
4	Correct	11 ms	5976 KB	Output is correct
5	Correct	12 ms	6324 KB	Output is correct
6	Correct	13 ms	6280 KB	Output is correct
7	Correct	10 ms	6348 KB	Output is correct
8	Correct	11 ms	6360 KB	Output is correct
9	Correct	10 ms	6344 KB	Output is correct
10	Correct	10 ms	6104 KB	Output is correct
11	Correct	11 ms	6104 KB	Output is correct
12	Correct	11 ms	5840 KB	Output is correct
13	Correct	10 ms	5828 KB	Output is correct
14	Correct	12 ms	5840 KB	Output is correct
15	Correct	10 ms	5980 KB	Output is correct
16	Correct	11 ms	5856 KB	Output is correct
17	Correct	11 ms	5960 KB	Output is correct
18	Correct	11 ms	6100 KB	Output is correct
19	Correct	11 ms	6100 KB	Output is correct
20	Correct	11 ms	6464 KB	Output is correct
21	Correct	9 ms	6364 KB	Output is correct
22	Correct	10 ms	6116 KB	Output is correct
23	Correct	11 ms	6368 KB	Output is correct
24	Correct	11 ms	6176 KB	Output is correct
25	Correct	11 ms	6356 KB	Output is correct
26	Correct	11 ms	6340 KB	Output is correct
27	Correct	11 ms	6380 KB	Output is correct
28	Correct	10 ms	6396 KB	Output is correct
29	Correct	10 ms	6132 KB	Output is correct
30	Correct	10 ms	6100 KB	Output is correct
31	Correct	2 ms	4496 KB	Output is correct
32	Correct	2 ms	4496 KB	Output is correct
33	Correct	3 ms	4500 KB	Output is correct
34	Correct	3 ms	4500 KB	Output is correct
35	Correct	2 ms	4504 KB	Output is correct
36	Correct	3 ms	4496 KB	Output is correct
37	Correct	2 ms	4496 KB	Output is correct
38	Correct	2 ms	4496 KB	Output is correct
39	Correct	2 ms	4496 KB	Output is correct
40	Correct	2 ms	4500 KB	Output is correct
41	Correct	2 ms	4500 KB	Output is correct
42	Correct	2 ms	4512 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4500 KB	Output is correct
2	Correct	2 ms	4496 KB	Output is correct
3	Correct	2 ms	4500 KB	Output is correct
4	Correct	3 ms	4788 KB	Output is correct
5	Correct	3 ms	4784 KB	Output is correct
6	Correct	3 ms	4792 KB	Output is correct
7	Correct	3 ms	4796 KB	Output is correct
8	Correct	3 ms	4784 KB	Output is correct
9	Correct	9 ms	6876 KB	Output is correct
10	Correct	9 ms	6872 KB	Output is correct
11	Correct	9 ms	6876 KB	Output is correct
12	Correct	2 ms	4504 KB	Output is correct
13	Correct	2 ms	4508 KB	Output is correct
14	Correct	2 ms	4500 KB	Output is correct
15	Correct	2 ms	4500 KB	Output is correct

Subtask #4
55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	7328 KB	Output is correct
2	Correct	18 ms	7260 KB	Output is correct
3	Correct	18 ms	7332 KB	Output is correct
4	Correct	11 ms	6092 KB	Output is correct
5	Correct	11 ms	6616 KB	Output is correct
6	Correct	15 ms	6296 KB	Output is correct
7	Correct	11 ms	6324 KB	Output is correct
8	Correct	11 ms	6104 KB	Output is correct
9	Correct	11 ms	6112 KB	Output is correct
10	Correct	11 ms	6112 KB	Output is correct
11	Correct	10 ms	6112 KB	Output is correct
12	Correct	10 ms	5840 KB	Output is correct
13	Correct	10 ms	5820 KB	Output is correct
14	Correct	10 ms	5840 KB	Output is correct
15	Correct	10 ms	5980 KB	Output is correct
16	Correct	11 ms	5976 KB	Output is correct
17	Correct	10 ms	5976 KB	Output is correct
18	Correct	10 ms	6012 KB	Output is correct
19	Correct	10 ms	5976 KB	Output is correct
20	Correct	9 ms	6368 KB	Output is correct
21	Correct	9 ms	6360 KB	Output is correct
22	Correct	11 ms	6368 KB	Output is correct
23	Correct	10 ms	6224 KB	Output is correct
24	Correct	11 ms	6180 KB	Output is correct
25	Correct	11 ms	6336 KB	Output is correct
26	Correct	11 ms	6324 KB	Output is correct
27	Correct	10 ms	6364 KB	Output is correct
28	Correct	11 ms	6104 KB	Output is correct
29	Correct	10 ms	6088 KB	Output is correct
30	Correct	10 ms	6096 KB	Output is correct

Subtask #5
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	7312 KB	Output is correct
2	Correct	19 ms	7232 KB	Output is correct
3	Correct	18 ms	7300 KB	Output is correct
4	Correct	11 ms	5972 KB	Output is correct
5	Correct	10 ms	6656 KB	Output is correct
6	Correct	11 ms	6100 KB	Output is correct
7	Correct	13 ms	6104 KB	Output is correct
8	Correct	11 ms	6300 KB	Output is correct
9	Correct	10 ms	6364 KB	Output is correct
10	Correct	10 ms	6108 KB	Output is correct
11	Correct	10 ms	6104 KB	Output is correct
12	Correct	10 ms	5828 KB	Output is correct
13	Correct	10 ms	5848 KB	Output is correct
14	Correct	10 ms	5776 KB	Output is correct
15	Correct	10 ms	5968 KB	Output is correct
16	Correct	11 ms	5904 KB	Output is correct
17	Correct	10 ms	5976 KB	Output is correct
18	Correct	10 ms	6044 KB	Output is correct
19	Correct	11 ms	5972 KB	Output is correct
20	Correct	9 ms	6368 KB	Output is correct
21	Correct	9 ms	6432 KB	Output is correct
22	Correct	11 ms	6360 KB	Output is correct
23	Correct	11 ms	6260 KB	Output is correct
24	Correct	11 ms	6328 KB	Output is correct
25	Correct	10 ms	6320 KB	Output is correct
26	Correct	11 ms	6192 KB	Output is correct
27	Correct	11 ms	6356 KB	Output is correct
28	Correct	10 ms	6360 KB	Output is correct
29	Correct	11 ms	6352 KB	Output is correct
30	Correct	10 ms	6356 KB	Output is correct
31	Correct	2 ms	4508 KB	Output is correct
32	Correct	2 ms	4496 KB	Output is correct
33	Correct	2 ms	4512 KB	Output is correct
34	Correct	3 ms	4504 KB	Output is correct
35	Correct	2 ms	4496 KB	Output is correct
36	Correct	2 ms	4504 KB	Output is correct
37	Correct	2 ms	4504 KB	Output is correct
38	Correct	2 ms	4508 KB	Output is correct
39	Correct	2 ms	4500 KB	Output is correct
40	Correct	2 ms	4500 KB	Output is correct
41	Correct	2 ms	4500 KB	Output is correct
42	Correct	2 ms	4500 KB	Output is correct

Submission #828692

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 55.0 / 55.0

Subtask #5 17.0 / 17.0

Subtask #1
8.0 / 8.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
55.0 / 55.0

Subtask #5
17.0 / 17.0