Submission #712991

#	Time	Username	Problem	Language	Result	Execution time	Memory
712991		MrKustic	Flights (JOI22_flights)	C++17	66 / 100	345 ms	3516 KiB

Ali

#include <bits/stdc++.h>
#include "Ali.h"
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb emplace_back
#define x first
#define y second
#define ff first
#define ss second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pt;
typedef pair<ll, ll> ptll;
typedef complex<double> ftype;
//typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//typedef gp_hash_table<int, int> table;

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,sse3,ssse3,sse4.1,sse4.2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
*/

//-------------------------------------------

const int B = 7;

const int MAXN = 1e4 + 10;

vector<int> gr[MAXN], g[MAXN], comps[MAXN];
int color[MAXN];
int recolor[MAXN];
int clr = 0;
vector<int> all_roots;
int roots[MAXN];

int dfs(int v, int start, int p = -1){
    int siz = 1;
    for (int u: gr[v]){
        if (u != p){
            siz += dfs(u, start, v);
        }
    }
    if (siz >= 7 || v == start){
        all_roots.push_back(v);
        return 0;
    } else {
        if (p != -1){
            g[v].push_back(p);
            g[p].push_back(v);
        }
        return siz;
    }
}

void coloring(int v, int c, int p = -1){
    color[v] = c;
    for (int u: g[v]){
        if (u != p)
            coloring(u, c, v);
    }
}

void bfsRecolor(int v0){
    deque<pt> q;
    q.push_back({v0, -1});
    int currColor = 0;
    while (!q.empty()){
        auto [v, p] = q.front();
        q.pop_front();
        recolor[v] = currColor++;
        for (int u: comps[v]){
            if (u != p)
                q.push_back({u, v});
        }
    }
}

int id[MAXN];

void indexing(int v, int &num, int comp, int p = -1){
    id[v] = comp * (2 * B - 1) + num;
    num++;
    for (int u: g[v]){
        if (u != p)
            indexing(u, num, comp, v);
    }
}

int n;

void Init(int N, vector<int> U, vector<int> V){
    n = N;
    for (int i = 0; i < n; i++)
        gr[i].clear(), g[i].clear();
    for (int i = 0; i < n - 1; i++){
        int u, v;
        u = U[i], v = V[i];
        gr[u].push_back(v);
        gr[v].push_back(u);
    }
    int start = 0;
    for (; start < n && sz(gr[start]) == 3; start++);
    all_roots.clear();
    dfs(start, start);
    fill(color, color + n, -1);
    clr = 0;
    for (int i = 0; i < n; i++){
        if (color[i] == -1)
            coloring(i, clr++);
    }
    for (int i = 0; i < n; i++)
        comps[i].clear();
    for (int u = 0; u < n; u++){
        for (int v: gr[u]){
            if (color[u] != color[v])
                comps[color[u]].push_back(color[v]);
        }
    }
    fill(recolor, recolor + n, -1);
    bfsRecolor(0);
    for (int i = 0; i < n; i++){
        color[i] = recolor[color[i]];
    }
    fill(roots, roots + n, 0);
    for (int x: all_roots)
        roots[color[x]] = x;
    for (int rt = 0; rt < clr; rt++){
        int num = 0;
        indexing(roots[rt], num, rt);
    }
    set<int> ids;
    for (int i = 0; i < n; i++)
        ids.insert(id[i]);
    for (int i = 0; i < n; i++){
        SetID(i, id[i]);
    }
}

string encode(ll x, int len){
    string res;
    for (; x > 0; x /= 2){
        res += (char)(x % 2 + '0');
    }
    while (sz(res) < len)
        res += '0';
    reverse(all(res));
    return res;
}

ll decode(const string &s){
    ll ans = 0;
    for (char c: s){
        int val = (c - '0');
        ans = ans * 2 + val;
    }
    return ans;
}

void encodeComponent(int v, string &res, int p = -1){
    for (int u: g[v]){
        if (u != p){
            res += '1';
            encodeComponent(u, res, v);
            res += '0';
        }
    }
}

bool find_path(int v, int to, vector<int> &path, int p = -1){
    path.push_back(v);
    if (v == to){
        return true;
    }
    for (int u: gr[v]){
        if (u != p){
            if (find_path(u, to, path, v))
                return true;
        }
    }
    path.pop_back();
    return false;
}

pt parse(ll y){
    ll x = 1;
    while (y >= x){
        y -= x;
        x++;
    }
    x--;
    return {x, y};
}

string SendA(string s){
    auto [x, y] = parse(decode(s));
    string t1, t2;
    encodeComponent(roots[x], t1);
    encodeComponent(roots[y], t2);
    int d = 0;
    int num1, num2;
    num1 = num2 = 0;
    if (x != y){
        int p1 = 0, p2 = 0;
        for (int i = 0; i < n; i++){
            if (color[i] == x)
                p1 = i;
            if (color[i] == y)
                p2 = i;
        }
        vector<int> path;
        find_path(p1, p2, path);
        for (int i = 0; i < 2; i++){
            while (color[path[sz(path) - 1]] == color[path[sz(path) - 2]])
                path.pop_back();
            reverse(all(path));
        }
        d = sz(path) - 1;
        num1 = id[path[0]] % (2 * B - 1);
        num2 = id[path.back()] % (2 * B - 1);
    }
    while (sz(t1) < 25)
        t1.push_back('0');
    while (sz(t2) < 25)
        t2.push_back('0');
    string ret = encode(d, 14) + t1 + t2 + encode(num1, 4) + encode(num2, 4);
    return ret;
}

Benjamin

#include <bits/stdc++.h>
#include "Benjamin.h"
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb emplace_back
#define x first
#define y second
#define ff first
#define ss second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pt;
typedef pair<ll, ll> ptll;
typedef complex<double> ftype;
//typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//typedef gp_hash_table<int, int> table;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,sse3,ssse3,sse4.1,sse4.2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
*/

//-------------------------------------------

int x2, y2;
const int B1 = 7;

vector<int> T1[2 * B1];
vector<int> T2[2 * B1];

void buildT1(int v, string &s, int &fr){
    while (s.back() == '1'){
        int u = fr++;
        T1[v].push_back(u);
        T1[u].push_back(v);
        s.pop_back();
        buildT1(u, s, fr);
    }
    s.pop_back();
}

void buildT2(int v, string &s, int &fr){
    while (s.back() == '1'){
        int u = fr++;
        T2[v].push_back(u);
        T2[u].push_back(v);
        s.pop_back();
        buildT2(u, s, fr);
    }
    s.pop_back();
}

int find_dst1(int v, int to, int c, int p = -1){
    if (v == to)
        return c;
    for (int u: T1[v]){
        if (u != p){
            int tmp = find_dst1(u, to, c + 1, v);
            if (tmp != -1)
                return tmp;
        }
    }
    return -1;
}

int find_dst2(int v, int to, int c, int p = -1){
    if (v == to)
        return c;
    for (int u: T2[v]){
        if (u != p){
            int tmp = find_dst2(u, to, c + 1, v);
            if (tmp != -1)
                return tmp;
        }
    }
    return -1;
}

string encode1(ll x, int len){
    string res;
    for (; x > 0; x /= 2){
        res += (char)(x % 2 + '0');
    }
    while (sz(res) < len)
        res += '0';
    reverse(all(res));
    return res;
}

ll decode1(const string &s){
    ll ans = 0;
    for (char c: s){
        int val = (c - '0');
        ans = ans * 2 + val;
    }
    return ans;
}

string SendB(int N, int X, int Y){
    int x = X;
    int y = Y;
    x2 = x;
    y2 = y;
    x /= (2 * B1 - 1);
    y /= (2 * B1 - 1);
    if (x < y)
        swap(x, y), swap(x2, y2);
    return encode1(x * (x + 1) / 2 + y, 20);
}

int Answer(string s){
    int d = decode1(s.substr(0, 14));
    string t1 = s.substr(14, 25);
    string t2 = s.substr(39, 25);
    int num1 = decode1(s.substr(64, 4));
    int num2 = decode1(s.substr(68, 4));
    reverse(all(t1));
    reverse(all(t2));
    for (int i = 0; i < 2 * B1; i++)
        T1[i].clear(), T2[i].clear();
    int fr = 1;
    buildT1(0, t1, fr);
    fr = 1;
    buildT2(0, t2, fr);
    int u = x2 % (2 * B1 - 1);
    int v = y2 % (2 * B1 - 1);
    int ans = 0;
    if (x2 / (2 * B1 - 1) == y2 / (2 * B1 - 1)){
        ans = find_dst1(u, v, 0);
    } else {
        int d1 = find_dst1(u, num1, 0);
        int d2 = find_dst2(v, num2, 0);
        ans = d1 + d2 + d;
    }
    return ans;
}

Compilation message (stderr)

grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

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