oj.uz

Submission #712991

# Submission time Handle Problem Language Result Execution time Memory
712991 2023-03-20T18:18:13 Z MrKustic Flights (JOI22_flights) C++17
66 / 100
 345 ms 3516 KB 
#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;
}
#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

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1168 KB Output is correct
2 Correct 1 ms 1168 KB Output is correct
3 Correct 2 ms 1168 KB Output is correct
4 Correct 1 ms 1256 KB Output is correct
5 Correct 1 ms 1168 KB Output is correct
6 Correct 9 ms 2700 KB Output is correct
7 Correct 9 ms 2792 KB Output is correct
8 Correct 11 ms 2784 KB Output is correct
9 Correct 11 ms 2776 KB Output is correct
10 Correct 9 ms 2916 KB Output is correct
11 Correct 6 ms 2448 KB Output is correct
12 Correct 8 ms 2576 KB Output is correct
13 Correct 8 ms 2612 KB Output is correct
14 Correct 7 ms 2812 KB Output is correct
15 Correct 9 ms 3332 KB Output is correct
16 Correct 8 ms 2704 KB Output is correct

Subtask #2
51.0 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 1168 KB Output is partially correct
2 Partially correct 61 ms 3376 KB Output is partially correct
3 Partially correct 5 ms 1224 KB Output is partially correct
4 Partially correct 314 ms 2848 KB Output is partially correct
5 Partially correct 321 ms 2876 KB Output is partially correct
6 Partially correct 329 ms 2844 KB Output is partially correct
7 Partially correct 334 ms 3516 KB Output is partially correct
8 Partially correct 343 ms 2996 KB Output is partially correct
9 Partially correct 262 ms 3128 KB Output is partially correct
10 Partially correct 240 ms 3220 KB Output is partially correct
11 Partially correct 290 ms 2752 KB Output is partially correct
12 Partially correct 37 ms 2428 KB Output is partially correct
13 Partially correct 184 ms 2804 KB Output is partially correct
14 Partially correct 224 ms 2788 KB Output is partially correct
15 Partially correct 6 ms 1376 KB Output is partially correct
16 Partially correct 293 ms 3488 KB Output is partially correct
17 Partially correct 244 ms 3512 KB Output is partially correct
18 Partially correct 250 ms 3256 KB Output is partially correct
19 Partially correct 240 ms 3268 KB Output is partially correct
20 Partially correct 161 ms 3220 KB Output is partially correct
21 Partially correct 240 ms 3336 KB Output is partially correct
22 Partially correct 251 ms 2856 KB Output is partially correct
23 Partially correct 238 ms 2796 KB Output is partially correct
24 Partially correct 293 ms 2692 KB Output is partially correct
25 Partially correct 233 ms 2700 KB Output is partially correct
26 Partially correct 258 ms 2880 KB Output is partially correct
27 Partially correct 259 ms 2696 KB Output is partially correct
28 Partially correct 242 ms 2816 KB Output is partially correct
29 Partially correct 269 ms 2820 KB Output is partially correct
30 Partially correct 250 ms 2780 KB Output is partially correct
31 Partially correct 265 ms 2888 KB Output is partially correct
32 Partially correct 244 ms 2852 KB Output is partially correct
33 Partially correct 252 ms 2780 KB Output is partially correct
34 Partially correct 250 ms 3008 KB Output is partially correct
35 Partially correct 270 ms 2972 KB Output is partially correct
36 Partially correct 248 ms 2924 KB Output is partially correct
37 Partially correct 243 ms 2868 KB Output is partially correct
38 Partially correct 246 ms 2848 KB Output is partially correct
39 Partially correct 57 ms 2740 KB Output is partially correct
40 Partially correct 345 ms 3296 KB Output is partially correct