Submission #583221

#	Time	Username	Problem	Language	Result	Execution time	Memory
583221		balbit	Flights (JOI22_flights)	C++17	15 / 100	71 ms	2424 KiB

Ali

#include "Ali.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define f first
#define s second
#define pii pair<ll, ll>

#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__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 bug(...)
#define endl '\n'
#endif // BALBIT


namespace {

const int maxn = 1e4+2;
const int inf = 0x3f3f3f3f;
const int B = 15;

vector<int> g[maxn];
int dep[maxn];
vector<int> here[maxn]; // stuff in this group
vector<int> ord;
bool targ[maxn];
int who = -1;
int toid[maxn];

void dfs(int v, int p) {
    ord.pb(v);
    bool fc = 1;
    for (int u : g[v]) {
        if (u != p) {
            dep[u] = dep[v] + 1;
            dfs(u,v);
            ord.pb(v);
        }
    }
}

void CLR(){
    ord.clear();
    memset(targ, 0, sizeof targ);
    who = -1;
    REP(i,maxn) {
        g[i].clear(); dep[i] = 0; here[i].clear();
        toid[i] = 0;
    }
}

int finddst(int v, int p) {
    if (targ[v]) {
        who = v;
        return 0;
    }
    int re = inf;
    for (int u : g[v]) {
        if (u == p) continue;
        MN(re, 1+finddst(u,v));
    }
    return re;
}



int encode(pii p) {
    assert(p.f <= p.s);
    int re = 0;
    REP(i, p.s) {
        re += i+1;
    }
    re += p.f;
    return re;
}

pii decode(int x) {
    REP(i, 10000000) {
        if (x < i+1) {
            return {x,i};
        }
        x -= i+1;
    }

    assert(0);
}

}

#ifdef BALBIT

#endif // BALBIT

void Init(int N, std::vector<int> U, std::vector<int> V) {
//  variable_example++;
//  SetID(0, 0);
//  SetID(1, 1);
//  SetID(2, 2 * N + 19);

    CLR();

    REP(i, N-1) {
        g[U[i]].pb(V[i]); g[V[i]].pb(U[i]);
    }

    dfs(0, -1);
    memset(toid, -1, sizeof toid);
    REP(i,SZ(ord)) {
        here[i/B].pb(ord[i]);
        if (toid[ord[i]] == -1) {
            toid[ord[i]] = i;
        }
    }

    REP(i,N) {
        #ifdef BALBIT
        bug(i, toid[i]);
        #else

        SetID(i, toid[i]);
        #endif
    }
}

std::string SendA(std::string S) {

    assert(SZ(S) == 20);

    ll tint = 0;
    REP(i, SZ(S)) {
        if (S[i] == '1') tint += (1<<i);
    }

    pii p = decode(tint);
    int a = p.f, b = p.s;

    bug(a, b);
    #ifdef BALBIT
    for (int e : here[a]) bug(e);
    for (int e : here[b]) bug(e);

    #endif // BALBIT

    string ret;

    int rta=-1, rtb=-1;
    {
        for (int t : here[a]) {
            if (rta == -1 || dep[t] < dep[rta]) rta = t;
        }
        for (int t : here[b]) {
            if (rtb == -1 || dep[t] < dep[rtb]) rtb = t;
        }
    }

//    if (dep[rta] < dep[rta]) {
//        ret += '0';
//    }else{
//        ret += '1';
//        swap(a,b); swap(rta, rtb);
//        // b has to be the deeper group!!
//    }

    REP1(i,B-1) {
        if (i >= SZ(here[a])) {
            ret+='1';
        }else{
            ret+= (dep[here[a][i]] > dep[here[a][i-1]]) + '0';
        }
    }

    REP1(i,B-1) {
        if (i >= SZ(here[b])) {
            ret+='1';
        }else{
            ret+= (dep[here[b][i]] > dep[here[b][i-1]]) + '0';
        }
    }



    {
        int bestdst = inf;
        pii bestpair = {-1, -1};

        for (int t : here[b]) targ[t] = 1;
        REP(i, SZ(here[a])) {
            int e = here[a][i];
            int ar = finddst(e, -1);
            if (ar < bestdst) {
                bestdst = ar;
                int j = find(ALL(here[b]), who) - here[b].begin();
                bestpair = {i,j};
            }
        }

        REP(i,14) {
            ret += '0' + ((bestdst >> i) & 1);
        }

        bug(bestdst, bestpair.f, bestpair.s);

        REP(i,4) {
            ret += '0' + ((bestpair.f >> i) & 1);
        }

        REP(i,4) {
            ret += '0' + ((bestpair.s >> i) & 1);
        }
    }


  return ret;
}
#ifdef BALBIT
signed main(){
    int n = 9;
    vector<int> u = {0,0,3,3,1,1,6,7};
    vector<int> v = {3,6,2,1,5,7,8,4};
    Init(n,u,v);

    string ago = SendA("00100000000000000000");
    bug(ago);
    freopen("in", "w", stdout);
    cout<<ago<<endl;
}
#endif

Benjamin

#include "Benjamin.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define f first
#define s second
#define pii pair<ll, ll>

#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__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 bug(...)
#define endl '\n'
#endif // BALBIT




namespace {

int variable_example = 0;

const int maxn = 1e4+2;
const int inf = 0x3f3f3f3f;
const int B = 15;

int X, Y;
int encode(pii p) {
    assert(p.f <= p.s);
    int re = 0;
    REP(i, p.s) {
        re += i+1;
    }
    re += p.f;
    return re;
}

pii decode(int x) {
    pii re = {0,0};

    REP(i, 10000000) {
        if (x < i+1) {
            return {x,i};
        }
        x -= i+1;
    }
}

vector<int> g[B*2];
int par[B*2];



int finddst(int v, int targ, int p) {
    if (v==targ) {
        return 0;
    }
    int re = inf;
    for (int u : g[v]) {
        if (u == p) continue;
        MN(re, 1+finddst(u,targ,v));
    }
    return re;
}


int go(int gm, int p1, int p2) {

    bug(gm, p1, p2);

    memset(par, -1, sizeof par);
    REP(i,B*2) g[i].clear();

    int at = 0;
    REP(i, B-1) {
        if ((gm >> i) & 1) {
            // go down
            par[i+1] = at;
            g[at].pb(i+1); g[i+1].pb(at);
            at = i+1;
        }else{
            if (par[at] != -1) {
                at = par[at];
            }else{
                par[at] = i+1;
                g[at].pb(i+1); g[i+1].pb(at);
                at = par[at];
            }
        }
    }

    return finddst(p1, p2, -1);
}

}

std::string SendB(int N, int _X, int _Y) {
    X=_X; Y=_Y;
    if (X > Y) swap(X,Y);
    int a = X/B, b = Y/B;
    int hey = encode({a,b});
    assert(hey < (1<<20));
    string re;
    REP(i,20) {
        re += '0' + ((hey>>i) & 1);
    }
    return re;
}

int Answer(std::string T) {

    int at = 0;

    auto read = [&](int nb) {
        int re = 0;
        REP(i,nb) {
            if (T[at] == '1') re += (1<<i);
            ++at;
        }
        return re;
    };

    int g1 = read(B-1), g2 = read(B-1);

    int dst = read(14);

    int p1 = read(4), p2 = read(4);

    bug(p1, p2);

    if (X / B == Y / B) {
        p1 = p2 = X%B; dst = 0;
    }


    int d1 = go(g1, p1, X%B);
    int d2 = go(g2, p2, Y%B);
    bug(d1);
    bug(d2);

    return  d1 + d2 + dst;

}

#ifdef BALBIT
signed main(){
    string bgo = SendB(9,5,14);
    bug(bgo);

    int yom = Answer("01111111111111111111111111111111110011111111111111");
    bug(yom);

}
#endif

Compilation message (stderr)

Ali.cpp: In function 'void {anonymous}::dfs(int, int)':
Ali.cpp:47:10: warning: unused variable 'fc' [-Wunused-variable]
   47 |     bool fc = 1;
      |          ^~
Ali.cpp: At global scope:
Ali.cpp:82:5: warning: 'int {anonymous}::encode(std::pair<long long int, long long int>)' defined but not used [-Wunused-function]
   82 | int encode(pii p) {
      |     ^~~~~~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Benjamin.cpp: In function 'std::pair<long long int, long long int> {anonymous}::decode(int)':
Benjamin.cpp:52:9: warning: variable 're' set but not used [-Wunused-but-set-variable]
   52 |     pii re = {0,0};
      |         ^~
Benjamin.cpp: At global scope:
Benjamin.cpp:51:5: warning: 'std::pair<long long int, long long int> {anonymous}::decode(int)' defined but not used [-Wunused-function]
   51 | pii decode(int x) {
      |     ^~~~~~
Benjamin.cpp:34:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
   34 | int variable_example = 0;
      |     ^~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 0 / 85