oj.uz

Submission #529572

# Submission time Handle Problem Language Result Execution time Memory
529572 2022-02-23T08:03:45 Z balbit Amusement Park (JOI17_amusement_park) C++14
0 / 100
 41 ms 13372 KB 
#include "Joi.h"
#include <bits/stdc++.h>
//#define int ll
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

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


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

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++];
        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);
}


void Joi(int N, int M, int A[], int B[], long long X, int T) {

    buildtree(N,M,A,B);
    REP(i,N) {
        bug(i, which[i]);
        MessageBoard(i, (X>>which[i]) & 1);
//        REP(j, BB) {
//            cout<<SET[i].here[j]<<' ';
//        }
//        cout<<endl;
//        REP(j, BB) {
//            cout<<SET[i].deg[j]<<' ';
//        }
//        cout<<endl;
    }


    return;

}

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




#include "Ioi.h"
#include <bits/stdc++.h>
//#define int ll
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

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


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

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++];
        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);
    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;
    }
    Move(P);
    dfs2(P, -1, V);
    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
0 / 8.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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