Submission #916542

#	Time	Username	Problem	Language	Result	Execution time	Memory
916542		GusterGoose27	Flights (JOI22_flights)	C++17	0 / 100	8 ms	1848 KiB

Ali

#include "Ali.h"
#include <bits/stdc++.h>

namespace {

using namespace std;

const int MAXN = 1e4+5;
const int block = 20;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
int n;
vector<int> edges[MAXN];
int id[MAXN];
vector<int> has[MAXN];
int topo[MAXN]; // 0 down, 1 up
int dist[MAXN];
int par[MAXN];
int t = 0;

void reset() {
    for (int i = 0; i < MAXN; i++) {
        edges[i].clear();
        id[i] = 0;
        has[i].clear();
        topo[i] = 0;
        dist[i] = 0;
        par[i] = 0;
    }
    t = 0;
}

string make_str(ll v, int pad = -1) {
    string s = "";
    while (v) {
        s = ((char)('0'+(v&1)) + s);
        v /= 2;
    }
    if (pad != -1) {
        while (s.size() < pad) {
            s = '0'+s;
        }
    }
    return s;
}

ll make_int(string s) {
    ll v = 0;
    for (char c: s) {
        v *= 2;
        v += c-'0';
    }
    return v;
}

ll hsh(vector<pll> &code) {
    ll ret = 0;
    for (pll p: code) {
        ret *= p.second;
        ret += p.first;
    }
    return ret;
}

void inc(int &a, bool b) {
    a = 2*a+b;
}

void inc_ll(ll &a, bool b){
    a = 2*a+b;
}

void dfs(int cur, int p = -1) {
    id[cur] = t;
    has[(t++)/block].push_back(cur);
    for (int v: edges[cur]) {
        if (v == p) continue;
        inc(topo[(t-1)/block], 0); 
        dfs(v, cur);
        has[(t++)/block].push_back(cur);
    }
    inc(topo[(t-1)/block], 1);
}

pll encode_dist(vector<int> nodes1, vector<int> nodes2) {
    fill(dist, dist+n, MAXN);
    fill(par, par+n, -1);
    queue<int> vals;
    for (int i = 0; i < nodes1.size(); i++) {
        int v = nodes1[i];
        dist[v] = 0;
        vals.push(v);
        par[v] = i;
    }
    while (!vals.empty()) {
        int t = vals.front();
        vals.pop();
        for (int v: edges[t]) {
            if (dist[v] < MAXN) continue;
            dist[v] = 1+dist[t];
            par[v] = par[t];
        }
    }
    int b = 0;
    for (int i = 1; i < nodes2.size(); i++) {
        int v = nodes2[i];
        if (dist[v] < dist[nodes2[b]]) b = i;
    }
    int a = par[nodes2[b]];
    vector<pll> code;
    code.push_back(pll(a, block));
    code.push_back(pll(b, block));
    code.push_back(pll(dist[b]/2, MAXN/2));
    return pll(hsh(code), block*block*(MAXN/2));
}

}

void Init(int N, vector<int> u, vector<int> v) {
    reset();
    n = N;
    for (int i = 0; i < n-1; i++) {
        edges[u[i]].push_back(v[i]);
        edges[v[i]].push_back(u[i]);
    }
    fill(id, id+n, -1);
    for (int i = 0; i < n; i++) if (edges[i].size() < 3) {
        dfs(i);
        break;
    }
    for (int i = 0; i < n; i++) SetID(i, id[i]);
    // variable_example++;
    // SetID(0, 0);
    // SetID(1, 1);
    // SetID(2, 2 * N + 19);
}

string SendA(string S) {
    int v = make_int(S);
    int v1 = v >> 10;
    int v2 = v % (1<<10);
    // first, encode the trees (to be optimized)
    vector<pll> code;
    bool com = 0;
    pii inter;
    for (int j = 0; j < has[v2].size(); j++) {
        for (int i = 0; i < has[v1].size(); i++) {
            if (has[v1][i] == has[v2][j]) {
                inter = pii(i, j);
                com = 1;
                break;
            }
        }
        if (com) break;
    }
    // code.push_back(pll(com, 2));
    code.push_back(pll(topo[v1]/2, 1<<(block-1)));
    code.push_back(pll(topo[v2]/2, 1<<(block-1)));
    if (com && v1 != v2) {
        // now we just need to specify the first joining point.
        code.push_back(pll(inter.first, block));
        code.push_back(pll(inter.second, block));
        // and now, we are done!
        return '1'+make_str(hsh(code));
    }
    // get closest nodes
    code.push_back(encode_dist(has[v1], has[v2]));
    return '0'+make_str(hsh(code));
}

Benjamin

#include "Benjamin.h"
#include <bits/stdc++.h>

namespace {

using namespace std;

const int MAXN = 1e4+5;
const int block = 20;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
vector<ll> szs1({1<<(block-1), 1<<(block-1), block, block, MAXN/2});
vector<ll> szs2({1<<(block-1), 1<<(block-1), block, block});
int n, x, y;
vector<pii> edges[2*block];
int id[block+1];

vector<int> cpy_stck;
vector<int> stck;

void reset() {
    for (int i = 0; i < 2*block; i++) edges[i].clear();
    for (int i = 0; i <= block; i++) id[i] = 0;
    cpy_stck.clear();
}

string make_str(ll v, int pad = -1) {
    string s = "";
    while (v) {
        s = ((char)('0'+(v&1)) + s);
        v /= 2;
    }
    if (pad != -1) {
        assert(s.size() <= pad);
        while (s.size() < pad) {
            s = '0'+s;
        }
    }
    return s;
}

vector<ll> decode(ll hshed, vector<ll> szs) {
    vector<ll> res;
    for (int i = szs.size()-1; i >= 0; i--) {
        res.push_back(hshed % szs[i]);
        hshed /= szs[i];
    }
    reverse(res.begin(), res.end());
    return res;
}

ll make_int(string s) {
    ll v = 0;
    for (char c: s) {
        v *= 2;
        v += c-'0';
    }
    return v;
}

void make_edge(int a, int b, int w) {
    edges[a].push_back({b, w});
    edges[b].push_back({a, w});
}

void build_tree(int inc, string s, int p = 0, int lo = -1) {
    if (p == 0) {
        stck.clear();
        stck.push_back(inc+p);
    }
    if (p == lo) {
        if (cpy_stck.empty()) cpy_stck = stck;
        else {
            make_edge(cpy_stck.back(), stck.back(), 0);
            stck = cpy_stck;
        }
    }
    id[p] = stck.back();
    if (p == s.size()) return;
    if (s[p] == '0') {
        make_edge(stck.back(), inc+p+1, 1);
        stck.push_back(inc+p+1);
        build_tree(inc, s, p+1, lo);
    }
    if (s[p] == '1') {
        if (stck.size() == 1) {
            make_edge(stck.back(), inc+p+1, 1);
            stck.pop_back();
            stck.push_back(inc+p+1);
        }
        else stck.pop_back();
        build_tree(inc, s, p+1, lo);
    }
}

int get_dist(int cur, int tar, int p = -1) {
    if (cur == tar) return 0;
    for (pii e: edges[cur]) {
        int nxt = e.first;
        if (nxt == p) continue;
        int v = get_dist(nxt, tar, cur);
        if (v != -1) return v+e.second;
    }
    return -1;
}

}

string SendB(int N, int X, int Y) {
    reset();
    n = N;
    x = X;
    y = Y;
    return make_str(x/block, 10)+make_str(y/block, 10);
}

int Answer(string T) {
    ll v = make_int(T.substr(1));
    if (T[0] == '0') {
        vector<ll> nums = decode(v, szs1);
        build_tree(0, make_str(nums[0], min(19, 2*n-2-20*(x/20))));
        nums[2] = id[nums[2]];
        bool same_comp = (x/20 == y/20);
        x = id[x%20];
        if (!same_comp) {
            build_tree(block, make_str(nums[1], min(19, 2*n-2-20*(y/20))));
            nums[3] = id[nums[3]];
            y = id[y%20];
            make_edge(nums[2], nums[3]+block, 2*nums[4]+((nums[2]+nums[3])&1));
        }
        int ans = get_dist(x, (same_comp ? 0 : 20)+y);
        assert(ans != -1);
        return ans;
    }
    else {
        vector<ll> nums = decode(v, szs2);
        build_tree(0, make_str(nums[0], min(19, 2*n-2-20*(x/20))), 0, nums[2]);
        x = id[x%20];
        build_tree(block, make_str(nums[1], min(19, 2*n-2-20*(y/20))), 0, nums[3]);
        y = id[y%20];
        int ans = get_dist(x, 20+y);
        assert(ans != -1);
        return ans;
    }
}

Compilation message (stderr)

Ali.cpp: In function 'std::string {anonymous}::make_str({anonymous}::ll, int)':
Ali.cpp:43:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |         while (s.size() < pad) {
      |                ~~~~~~~~~^~~~~
Ali.cpp: In function '{anonymous}::pll {anonymous}::encode_dist(std::vector<int>, std::vector<int>)':
Ali.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 0; i < nodes1.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
Ali.cpp:108:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for (int i = 1; i < nodes2.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:149:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for (int j = 0; j < has[v2].size(); j++) {
      |                     ~~^~~~~~~~~~~~~~~~
Ali.cpp:150:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         for (int i = 0; i < has[v1].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~
Ali.cpp: At global scope:
Ali.cpp:72:6: warning: 'void {anonymous}::inc_ll({anonymous}::ll&, bool)' defined but not used [-Wunused-function]
   72 | void inc_ll(ll &a, bool b){
      |      ^~~~~~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Benjamin.cpp:2:
Benjamin.cpp: In function 'std::string {anonymous}::make_str({anonymous}::ll, int)':
Benjamin.cpp:37:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |         assert(s.size() <= pad);
      |                ~~~~~~~~~^~~~~~
Benjamin.cpp:38:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |         while (s.size() < pad) {
      |                ~~~~~~~~~^~~~~
Benjamin.cpp: In function 'void {anonymous}::build_tree(int, std::string, int, int)':
Benjamin.cpp:82:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     if (p == s.size()) return;
      |         ~~^~~~~~~~~~~

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