Submission #1058474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058474		j_vdd16	Flights (JOI22_flights)	C++17	0 / 100	36 ms	2252 KiB

Ali

#include "Ali.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

namespace {

    int n;
    vvi adj;

    vi specialIndices;
    vb isSpecial;
    vi parents;
    vii inOut;
    int counter;

    constexpr int MAX = 5;
    constexpr int MAX2 = 1 << MAX;

    int dfs(int node, int parent) {
        parents[node] = parent;
        inOut[node].first = counter++;

        int subtreeSize = 1;

        for (int child : adj[node]) {
            if (child == parent) continue;

            subtreeSize += dfs(child, node);
        }


        inOut[node].second = counter++;

        if (subtreeSize >= MAX2) {
            specialIndices.push_back(node);
            isSpecial[node] = true;
            return 0;
        }

        return subtreeSize;
    }

    bool isAncestor(int a, int b) {
        return inOut[a].first <= inOut[b].first && inOut[b].first <= inOut[a].second;
    }
    
    void dfsID(int node, int parent, int specialIndex, int& count) {
        SetID(node, specialIndex * MAX2 * 2 + (count++));

        for (int child : adj[node]) {
            if (child == parent || isSpecial[child]) continue;

            dfsID(child, node, specialIndex, count);
        }
    }
    void setIDS() {
        loop(i, specialIndices.size()) {
            int count = 0;
            dfsID(specialIndices[i], parents[specialIndices[i]], i, count);
        }
    }
}

void Init(int N, std::vector<int> U, std::vector<int> V) {
    n = N;
    adj = vvi(n);
    loop(i, n - 1) {
        adj[U[i]].push_back(V[i]);
        adj[V[i]].push_back(U[i]);
    }

    specialIndices = vi();
    isSpecial = vb(n);
    parents = vi(n);
    counter = 0;
    inOut = vii(n);
    dfs(0, 0);
    if (!isSpecial[0]) {
        isSpecial[0] = true;
        specialIndices.push_back(0);
    }

    setIDS();
}

namespace {

    int distanceDfs(int node, int parent, int goal) {
        if (node == goal) return 0;

        for (int child : adj[node]) {
            if (child == parent) continue;

            int res = distanceDfs(child, node, goal);
            if (res >= 0) return res + 1;
        }

        return -1;
    }
    void treeCode(int node, string& code) {
        int childCount = 0;
        for (int child : adj[node]) {
            if (child == parents[node] || isSpecial[child]) continue;

            childCount++;
            code.push_back('1');

            treeCode(child, code);
        }

        if (childCount < 2)
            code.push_back('0');
    }

    int closestLeafDfs(int node, int goal, int& leafCounter) {
        int childCount = 0;
        for (int child : adj[node]) {
            if (child == parents[node] || isSpecial[child]) continue;

            childCount++;
            int res = closestLeafDfs(child, goal, leafCounter);
            if (res >= 0) return res;
        }
        
        if (childCount == 0) {
            if (isAncestor(node, goal)) {
                return node;
            }
            leafCounter++;
        }

        return -1;
    }
}

std::string SendA(std::string S) { //return max 24 is optimal
    int idx1 = 0, idx2 = 0;
    loop(i, 10) {
        idx1 += (S[i] == '1') * (1 << i);
    }
    loop(i, 10) {
        idx2 += (S[i + 10] == '1') * (1 << i);
    }
    int node1 = specialIndices[idx1];
    int node2 = specialIndices[idx2];

    
    string code1, code2;
    treeCode(node1, code1);
    treeCode(node2, code2);
    
    cerr << "Code 1: " << code1 << endl;
    cerr << "Code 2: " << code2 << endl;

    if (node1 == node2) {
        int dist = distanceDfs(node1, -1, node2);
        string result(14, '0');
        loop(i, 14) {
            if (dist & (1 << i)) result[i] = '1';
        }

        return result + code1;
    }

    string extra;
    if (isAncestor(node1, node2)) {
        int leafCounter = 0;
        int closest = closestLeafDfs(node1, node2, leafCounter);
        extra += "10";

        while (leafCounter) {
            if (leafCounter % 2) 
                extra.push_back('1');
            else 
                extra.push_back('0');

            leafCounter /= 2;
        }

        node1 = closest;
    }
    else if (isAncestor(node2, node1)) {
        int leafCounter = 0;
        int closest = closestLeafDfs(node2, node1, leafCounter);
        extra += "11";

        while (leafCounter) {
            if (leafCounter % 2) 
                extra.push_back('1');
            else 
                extra.push_back('0');

            leafCounter /= 2;
        }

        node2 = closest;
    }
    else {
        extra.push_back('0');
    }

    int dist = distanceDfs(node1, -1, node2);
    string result(14, '0');
    loop(i, 14) {
        if (dist & (1 << i)) result[i] = '1';
    }

    return result + code1 + code2 + extra;
}

Benjamin

#include "Benjamin.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

namespace {

    int x, y;

    constexpr int MAX = 5;
}

std::string SendB(int N, int X, int Y) {
    cerr << "X: " << X << ", Y: " << Y << endl;

    x = X;
    y = Y;

    X >>= MAX + 1;
    Y >>= MAX + 1;
    //log2(N) < 14

    string out(20, '0');
    loop(i, 10) {
        if (X & (1 << i)) out[i] = '1';
    }
    loop(i, 10) {
        if (Y & (1 << i)) out[10 + i] = '1';
    }

    return out;
}

namespace {
    void parse(vii& children, vi& parents, vvi& adj, vi& leaves, const string& T, int& i) {
        children = { { -1, -1} };
        parents = { -1 };
        adj = vvi(1);

        int node = 0;
        while (true) {
            bool bit = T[i++] == '1';
        
            if (bit) {
                parents.push_back(node);
                adj.push_back({});
                children.push_back({ -1, -1 });
                int next = (int)parents.size() - 1;
                adj[node].push_back(next);
                adj[next].push_back(node);

                if (children[node].first == -1) {
                    children[node].first = next;
                }
                else {
                    children[node].second = next;
                }
                node = next;
            }
            else {
                if (parents[node] == -1) {
                    break;
                }

                if (children[node].first == -1) leaves.push_back(node);
                node = parents[node];
                
                while (parents[node] != -1 && children[node].second >= 0)
                    node = parents[node];

                if (children[node].second >= 0 && parents[node] == -1) {
                    break;
                }
            }
        }
    }

    int distanceDfs(const vvi& adj, int node, int parent, int goal) {
        if (node == goal) return 0;

        for (int child : adj[node]) {
            if (child == parent) continue;

            int res = distanceDfs(adj, child, node, goal);
            if (res >= 0) return res + 1;
        }

        return -1;
    }
}

int Answer(std::string T) {
    cerr << "T: " << T << endl;

    int dist = 0;
    int i = 0;
    for (; i < 14; i++) {
        if (T[i] == '1')
            dist += (1 << i);
    }

    cerr << "Dist: " << dist << endl;
    cerr << "Rest: " << T.substr(i) << endl;

    int node1 = x & ((1 << (MAX + 1)) - 1);
    int node2 = y & ((1 << (MAX + 1)) - 1);

    vii children1, children2;
    vi parents1, parents2;
    vvi adj1, adj2;
    vi leaves1, leaves2;
    
    parse(children1, parents1, adj1, leaves1, T, i);
    if ((x >> (MAX + 1)) == (y >> (MAX + 1))) {
        return distanceDfs(adj1, node1, -1, node2);
    }

    parse(children2, parents2, adj2, leaves2, T, i);

    int start1 = 0, start2 = 0;
    if (T[i++] == '1') {
        bool nextBit = T[i++] == '1';
        
        int leafIdx = 0;
        int startIdx = i;
        while (i < T.size()) {
            leafIdx += (T[i] == '1') * (1 << (i - startIdx));
            i++;
        }

        if (nextBit) {
            start2 = leaves2[leafIdx];
        }
        else {
            start1 = leaves1[leafIdx];
        }
    }

    dist += distanceDfs(adj1, start1, -1, node1);
    dist += distanceDfs(adj2, start2, -1, node2);

    return dist;
}

Compilation message (stderr)

Ali.cpp: In function 'void {anonymous}::setIDS()':
Ali.cpp:19:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define loop(X, N) for(int X = 0; X < (N); X++)
      |                                     ^
Ali.cpp:85:9: note: in expansion of macro 'loop'
   85 |         loop(i, specialIndices.size()) {
      |         ^~~~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Benjamin.cpp: In function 'int Answer(std::string)':
Benjamin.cpp:153:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |         while (i < T.size()) {
      |                ~~^~~~~~~~~~

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