Submission #916536

#	Time	Username	Problem	Language	Result	Execution time	Memory
916536		GusterGoose27	Flights (JOI22_flights)	C++17	0 / 100	5 ms	1728 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 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;
    code.push_back(pll(topo[v1]/2, 1<<(block-1)));
    code.push_back(pll(topo[v2]/2, 1<<(block-1)));
    // get closest nodes
    code.push_back(encode_dist(has[v1], has[v2]));
    return 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> szs({1<<(block-1), 1<<(block-1), block, block, MAXN/2});
int n, x, y;
vector<pii> edges[2*block];

void reset() {
    for (int i = 0; i < 2*block; i++) edges[i].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> 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;
}

vector<int> stck;

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

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

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);
    vector<ll> nums = decode(v);
    build_tree(0, make_str(nums[0], min(19, 2*n-2-20*(x/20))));
    if (x/20 != y/20) build_tree(block, make_str(nums[1], min(20, 2*n-1-20*(y/20))));
    if (x/20 != y/20) make_edge(nums[2], nums[3]+block, 2*nums[4]+((nums[2]+nums[3])&1));
    int ans = get_dist(x%20, ((x/20 == y/20) ? 0 : 20)+(y%20));
    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:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0; i < nodes1.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
Ali.cpp:104:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for (int i = 1; i < nodes2.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
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:30:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |         assert(s.size() <= pad);
      |                ~~~~~~~~~^~~~~~
Benjamin.cpp:31:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |         while (s.size() < pad) {
      |                ~~~~~~~~~^~~~~

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