oj.uz

Submission #529602

# Submission time Handle Problem Language Result Execution time Memory
529602 2022-02-23T08:55:25 Z balbit Amusement Park (JOI17_amusement_park) C++14
100 / 100
 86 ms 24476 KB 
#include "Joi.h"
#include <bits/stdc++.h>
//#define int ll
#undef BALBIT
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif



namespace {
const int maxn = 1e4+5;
vector<int> g[maxn];
int dpar[maxn];
int find(int x) {
    return x == dpar[x]? x : dpar[x] = find(dpar[x]);
}

const int BB = 60;

struct nxt{
    int here[BB+1], deg[BB+1];
    void cpy(nxt y) {
        REP(i, BB) here[i] = y.here[i], deg[i] = y.deg[i];
    }
    nxt(){
        memset(here, 0, sizeof here);
        memset(deg, 0, sizeof deg);
    }
};

nxt SET[maxn];
bool seen[maxn];
bool ininit[maxn]; // is it in the initial set

vector<pii> edges;
bool hasedge(int a, int b) {
    if (a > b) swap(a,b);
    return binary_search(ALL(edges), pii{a,b});
}

vector<int> bfs(int start) {
    vector<int> re;
    int at = 0;
    re.pb(start);
    seen[start] = 1;

    memset(seen, 0, sizeof seen);

    while (at < SZ(re) && SZ(re) < BB) {
        int v = re[at++]; seen[v] = 1;
        for (int u : g[v]) {
            if (!seen[u] && SZ(re) < BB) {
                re.pb(u);
            }
        }
    }
    assert(SZ(re) == BB);
    return re;
}

int which[maxn]; // which bit does this node correspond to?

void dfs(int v, int p) {
    if (ininit[v]) {
        SET[v].cpy( SET[0] );
    }else{
        SET[v].cpy( SET[p] );
        bool remleaf = 0;
        REP(i, BB) {
            if (SET[v].deg[i] == 1 && SET[v].here[i] != p && !remleaf) {
                remleaf = 1;
                int u = SET[v].here[i]; // the leaf to be removed
                REP(j, BB) {
                    // might need to update your degree
                    if (hasedge(u, SET[v].here[j])) {
                        SET[v].deg[j]--;
                        break;
                    }
                }
                SET[v].here[i] = v; // new leaf!
                SET[v].deg[i] = 1;
            }
            if (SET[v].here[i] == p) {
                // one more child
                SET[v].deg[i] ++;
            }
        }
        assert(remleaf);
    }
    REP(i, BB) {
        which[SET[v].here[i]] = i;
    }
    for (int u : g[v]) {
        if (u != p) {
            dfs(u, v);
        }
    }
}

void buildtree(int N, int M, int A[], int B[]) {
    REP(i,N) {
        dpar[i] = i;
    }
    REP(i,M) {
        if (find(A[i]) != find(B[i])) {
            dpar[find(A[i])] = find(B[i]);
            g[A[i]].pb(B[i]);
            g[B[i]].pb(A[i]);
            int a = A[i], b = B[i];
            if (a > b) swap(a,b);
            edges.pb({a,b});
        }
    }
    sort(ALL(edges));
    bug(SZ(edges));

    vector<int> frst = bfs(0);
    REP(i,BB) {
        SET[0].here[i] = frst[i];
        ininit[frst[i]] = 1;
    }
    map<int, int> tmpmp;
    REP(i,BB) {
        int v = frst[i];
        for (int u : g[v]) {
            ++tmpmp[u];
        }
    }
    REP(i,BB) {
        SET[0].deg[i] = tmpmp[SET[0].here[i]];
//        cout<<"FFFF "<<SET[0].here[i]<<' '<< SET[0].deg[i]<<endl;
    }

    dfs(0, -1);
}

};


void Joi(int N, int M, int A[], int B[], long long X, int T) {
//    cout<<X<<endl;
    buildtree(N,M,A,B);

    REP(i,N) {
        bug(i, which[i]);
//        cout<<"Which? "<<i<<' '<<which[i]<<endl;
//        REP(j, BB) {
//            cout<<SET[i].here[j]<<' ';
//        }
//        cout<<endl;
//        REP(j, BB) {
//            cout<<SET[i].deg[j]<<' ';
//        }
//        cout<<endl;
#ifdef BALBIT
#else
        MessageBoard(i, (X>>which[i]) & 1);

#endif
    }


    return;

}

#ifdef BALBIT
int AA[] = {0, 0, 0, 1, 2, 2, 6, 4, 3};
int CC[] = {1, 2, 3, 4, 5, 6, 7, 2, 1};
//
signed main(){
    Joi(8, 9,
        AA,CC,
        10,
        10
        );
}
#endif




#include "Ioi.h"
#include <bits/stdc++.h>
//#define int ll
#undef BALBIT
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif


namespace {

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


const int maxn = 1e4+5;

vector<int> g[maxn];
int dpar[maxn];
int find(int x) {
    return x == dpar[x]? x : dpar[x] = find(dpar[x]);
}

const int BB = 60;

struct nxt{
    int here[BB+1], deg[BB+1];
    void cpy(nxt y) {
        REP(i, BB) here[i] = y.here[i], deg[i] = y.deg[i];
    }
    nxt(){
        memset(here, 0, sizeof here);
        memset(deg, 0, sizeof deg);
    }
};

nxt SET[maxn];
bool seen[maxn];
bool ininit[maxn]; // is it in the initial set

vector<pii> edges;
bool hasedge(int a, int b) {
    if (a > b) swap(a,b);
    return binary_search(ALL(edges), pii{a,b});
}

vector<int> bfs(int start) {
    vector<int> re;
    int at = 0;
    re.pb(start);

    memset(seen, 0, sizeof seen);

    while (at < SZ(re) && SZ(re) < BB) {
        int v = re[at++]; seen[v] = 1;
        for (int u : g[v]) {
            if (!seen[u] && SZ(re) < BB) {
                re.pb(u);
            }
        }
    }
    assert(SZ(re) == BB);
    return re;
}

int which[maxn]; // which bit does this node correspond to?

void dfs(int v, int p) {
    if (ininit[v]) {
        SET[v].cpy( SET[0] );
    }else{
        SET[v].cpy( SET[p] );
        bool remleaf = 0;
        REP(i, BB) {
            if (SET[v].deg[i] == 1 && SET[v].here[i] != p && !remleaf) {
                remleaf = 1;
                int u = SET[v].here[i]; // the leaf to be removed
                REP(j, BB) {
                    // might need to update your degree
                    if (hasedge(u, SET[v].here[j])) {
                        SET[v].deg[j]--;
                        break;
                    }
                }
                SET[v].here[i] = v; // new leaf!
                SET[v].deg[i] = 1;
            }
            if (SET[v].here[i] == p) {
                // one more child
                SET[v].deg[i] ++;
            }
        }
    }
    REP(i, BB) {
        which[SET[v].here[i]] = i;
    }
    for (int u : g[v]) {
        if (u != p) {
            dfs(u, v);
        }
    }
}

void buildtree(int N, int M, int A[], int B[]) {
    REP(i,N) {
        dpar[i] = i;
    }
    REP(i,M) {
        if (find(A[i]) != find(B[i])) {
            dpar[find(A[i])] = find(B[i]);
            g[A[i]].pb(B[i]);
            g[B[i]].pb(A[i]);
            int a = A[i], b = B[i];
            if (a > b) swap(a,b);
            edges.pb({a,b});
        }
    }
    sort(ALL(edges));

    vector<int> frst = bfs(0);
    REP(i,BB) {
        SET[0].here[i] = frst[i];
        ininit[frst[i]] = 1;
    }
    map<int, int> tmpmp;
    REP(i,BB) {
        int v = frst[i];
        for (int u : g[v]) {
            ++tmpmp[u];
        }
    }
    REP(i,BB) {
        SET[0].deg[i] = tmpmp[SET[0].here[i]];
    }

    dfs(0, -1);
}



bool okay[maxn]; // in my designated spanned tree
int whichbit[maxn]; // which bit does it help
ll ret =0 ;

#ifdef BALBIT
int Move(int u) {
    bug(u);
    int x; cin>>x;
    return x;
}
#endif // BALBIT

void dfs2(int v, int p, int val) {
    ret |= ((1ll<<whichbit[v]) * val);
//    cout<<"HI "<<v<<' '<<val<<endl;
    for (int u : g[v]) {
        if (okay[u] && u != p) {
            dfs2(u, v, Move(u));
        }
    }
    if (p != -1) {
        Move(p);
    }
}

};


long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    buildtree(N,M,A,B);
    REP(i, BB) {
        okay[SET[P].here[i]] = 1;
        whichbit[SET[P].here[i]] = i;
    }
    dfs2(P, -1, V);
//    cout<<V<<endl;
//    cout<<ret<<endl;
    return ret;
}


//int AA[] = {0, 0, 0, 1, 2, 2, 6};
//int CC[] = {1, 2, 3, 4, 5, 6, 7};
//
//signed main(){
//    Ioi(8, 7,
//        AA,CC,
//        7,
//        1,
//        -1
//        );
//}

/*

*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10748 KB Output is correct
2 Correct 7 ms 10704 KB Output is correct
3 Correct 6 ms 10748 KB Output is correct
4 Correct 8 ms 10740 KB Output is correct
5 Correct 7 ms 10720 KB Output is correct
6 Correct 9 ms 10748 KB Output is correct
7 Correct 6 ms 10748 KB Output is correct
8 Correct 6 ms 10744 KB Output is correct
9 Correct 6 ms 10744 KB Output is correct
10 Correct 6 ms 10748 KB Output is correct
11 Correct 9 ms 10944 KB Output is correct
12 Correct 6 ms 10748 KB Output is correct
13 Correct 6 ms 10752 KB Output is correct
14 Correct 6 ms 10752 KB Output is correct
15 Correct 6 ms 10752 KB Output is correct
16 Correct 7 ms 10748 KB Output is correct
17 Correct 6 ms 10744 KB Output is correct
18 Correct 6 ms 10752 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 13096 KB Output is correct
2 Correct 71 ms 13560 KB Output is correct
3 Correct 49 ms 13588 KB Output is correct
4 Correct 31 ms 12800 KB Output is correct
5 Correct 61 ms 18144 KB Output is correct
6 Correct 65 ms 16584 KB Output is correct
7 Correct 59 ms 16596 KB Output is correct
8 Correct 62 ms 17356 KB Output is correct
9 Correct 61 ms 17424 KB Output is correct
10 Correct 32 ms 13520 KB Output is correct
11 Correct 35 ms 13520 KB Output is correct
12 Correct 38 ms 12688 KB Output is correct
13 Correct 27 ms 12668 KB Output is correct
14 Correct 31 ms 12708 KB Output is correct
15 Correct 34 ms 12912 KB Output is correct
16 Correct 33 ms 12852 KB Output is correct
17 Correct 34 ms 12816 KB Output is correct
18 Correct 38 ms 12672 KB Output is correct
19 Correct 32 ms 12864 KB Output is correct
20 Correct 40 ms 18704 KB Output is correct
21 Correct 41 ms 18544 KB Output is correct
22 Correct 72 ms 15608 KB Output is correct
23 Correct 75 ms 17352 KB Output is correct
24 Correct 63 ms 16104 KB Output is correct
25 Correct 68 ms 16796 KB Output is correct
26 Correct 72 ms 17496 KB Output is correct
27 Correct 61 ms 17396 KB Output is correct
28 Correct 72 ms 17680 KB Output is correct
29 Correct 59 ms 16628 KB Output is correct
30 Correct 70 ms 16600 KB Output is correct
31 Correct 5 ms 10740 KB Output is correct
32 Correct 8 ms 10776 KB Output is correct
33 Correct 8 ms 10752 KB Output is correct
34 Correct 7 ms 10752 KB Output is correct
35 Correct 7 ms 10732 KB Output is correct
36 Correct 7 ms 10752 KB Output is correct
37 Correct 7 ms 10740 KB Output is correct
38 Correct 7 ms 10748 KB Output is correct
39 Correct 6 ms 10776 KB Output is correct
40 Correct 7 ms 10776 KB Output is correct
41 Correct 6 ms 10736 KB Output is correct
42 Correct 7 ms 10740 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10736 KB Output is correct
2 Correct 7 ms 10748 KB Output is correct
3 Correct 5 ms 10784 KB Output is correct
4 Correct 11 ms 12780 KB Output is correct
5 Correct 12 ms 12828 KB Output is correct
6 Correct 12 ms 12824 KB Output is correct
7 Correct 10 ms 12832 KB Output is correct
8 Correct 12 ms 12832 KB Output is correct
9 Correct 47 ms 24344 KB Output is correct
10 Correct 40 ms 24380 KB Output is correct
11 Correct 39 ms 24476 KB Output is correct
12 Correct 6 ms 10748 KB Output is correct
13 Correct 6 ms 10748 KB Output is correct
14 Correct 7 ms 10740 KB Output is correct
15 Correct 6 ms 10736 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 13112 KB Output is correct
2 Correct 62 ms 13476 KB Output is correct
3 Correct 61 ms 13488 KB Output is correct
4 Correct 30 ms 12828 KB Output is correct
5 Correct 70 ms 21160 KB Output is correct
6 Correct 55 ms 17416 KB Output is correct
7 Correct 67 ms 17268 KB Output is correct
8 Correct 64 ms 15076 KB Output is correct
9 Correct 65 ms 16084 KB Output is correct
10 Correct 32 ms 13700 KB Output is correct
11 Correct 33 ms 13648 KB Output is correct
12 Correct 36 ms 12656 KB Output is correct
13 Correct 39 ms 12520 KB Output is correct
14 Correct 41 ms 12696 KB Output is correct
15 Correct 38 ms 12852 KB Output is correct
16 Correct 31 ms 12776 KB Output is correct
17 Correct 32 ms 12836 KB Output is correct
18 Correct 33 ms 12768 KB Output is correct
19 Correct 32 ms 12816 KB Output is correct
20 Correct 36 ms 18704 KB Output is correct
21 Correct 34 ms 18472 KB Output is correct
22 Correct 72 ms 17048 KB Output is correct
23 Correct 72 ms 16504 KB Output is correct
24 Correct 77 ms 16508 KB Output is correct
25 Correct 71 ms 17476 KB Output is correct
26 Correct 65 ms 17096 KB Output is correct
27 Correct 77 ms 18124 KB Output is correct
28 Correct 73 ms 15948 KB Output is correct
29 Correct 63 ms 16288 KB Output is correct
30 Correct 56 ms 16872 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 13236 KB Output is correct
2 Correct 57 ms 13508 KB Output is correct
3 Correct 56 ms 13508 KB Output is correct
4 Correct 37 ms 12800 KB Output is correct
5 Correct 69 ms 22460 KB Output is correct
6 Correct 67 ms 16120 KB Output is correct
7 Correct 66 ms 15816 KB Output is correct
8 Correct 53 ms 17404 KB Output is correct
9 Correct 67 ms 16760 KB Output is correct
10 Correct 33 ms 13580 KB Output is correct
11 Correct 27 ms 13628 KB Output is correct
12 Correct 31 ms 12648 KB Output is correct
13 Correct 35 ms 12716 KB Output is correct
14 Correct 37 ms 12664 KB Output is correct
15 Correct 46 ms 12720 KB Output is correct
16 Correct 36 ms 12960 KB Output is correct
17 Correct 28 ms 12876 KB Output is correct
18 Correct 28 ms 12816 KB Output is correct
19 Correct 31 ms 12820 KB Output is correct
20 Correct 35 ms 18568 KB Output is correct
21 Correct 43 ms 18440 KB Output is correct
22 Correct 86 ms 16852 KB Output is correct
23 Correct 72 ms 16348 KB Output is correct
24 Correct 64 ms 16332 KB Output is correct
25 Correct 67 ms 16628 KB Output is correct
26 Correct 70 ms 15780 KB Output is correct
27 Correct 67 ms 18192 KB Output is correct
28 Correct 74 ms 18360 KB Output is correct
29 Correct 68 ms 17544 KB Output is correct
30 Correct 65 ms 17212 KB Output is correct
31 Correct 8 ms 10740 KB Output is correct
32 Correct 6 ms 10740 KB Output is correct
33 Correct 6 ms 10724 KB Output is correct
34 Correct 8 ms 10740 KB Output is correct
35 Correct 6 ms 10740 KB Output is correct
36 Correct 7 ms 10736 KB Output is correct
37 Correct 6 ms 10740 KB Output is correct
38 Correct 7 ms 10740 KB Output is correct
39 Correct 6 ms 10740 KB Output is correct
40 Correct 7 ms 10724 KB Output is correct
41 Correct 7 ms 10748 KB Output is correct
42 Correct 10 ms 10740 KB Output is correct