Submission #333030

#	Time	Username	Problem	Language	Result	Execution time	Memory
333030		dolphingarlic	Grad (COI14_grad)	C++14	0 / 100	493 ms	126316 KiB

grad

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

struct Point { int x, y; } p[101010];

struct SP;

struct Node { // Node in tree decomposition
    int idx[2];
    double dist;

    Node(int _u, int _v) : dist(hypot(p[_u].x - p[_v].x, p[_u].y - p[_v].y)) {
        idx[0] = _u;
        idx[1] = _v;
    }

    vector<Node *> children;
    vector<Node *> anc;

    vector<SP> anc_sp;
};

struct SP { // Shortest path between two nodes in tree decomposition
    int idx[2][2];
    double cost[2][2];

    SP(Node *u) {
        idx[0][0] = idx[1][0] = u->idx[0];
        idx[0][1] = idx[1][1] = u->idx[1];

        cost[0][0] = cost[1][1] = 0;
        cost[0][1] = cost[1][0] = u->dist;
    }

    SP(Node *u, Node *v) {
        assert(u->anc[0] == v);

        idx[0][0] = u->idx[0], idx[0][1] = u->idx[1];
        idx[1][0] = v->idx[0], idx[1][1] = v->idx[1];

        if (u->idx[0] == v->idx[0]) {
            cost[0][0] = 0;
            cost[0][1] = v->dist;
            cost[1][0] = u->dist;
            cost[1][1] = u->dist + v->dist;
        } else {
            cost[0][0] = v->dist;
            cost[0][1] = 0;
            cost[1][0] = u->dist + v->dist;
            cost[1][1] = u->dist;
        }
    }

    SP(SP a, SP b) {
        if (a.idx[1][0] == b.idx[1][0] && a.idx[1][1] == b.idx[1][1]) {
            swap(b.idx[0][0], b.idx[1][0]);
            swap(b.idx[0][1], b.idx[1][1]);
            swap(b.cost[0][1], b.cost[1][0]);
        }
        assert(a.idx[1][0] == b.idx[0][0] && a.idx[1][1] == b.idx[0][1]);

        idx[0][0] = a.idx[0][0], idx[0][1] = a.idx[0][1];
        idx[1][0] = b.idx[1][0], idx[1][1] = b.idx[1][1];

        for (int i : {0, 1}) for (int j : {0, 1})
            cost[i][j] = min(a.cost[i][0] + b.cost[0][j], a.cost[i][1] + b.cost[1][j]);
    }
};

struct City { // City in original graph
    int depth; // Depth in tree decomposition
    Node *node[2];

    City(int _d = -1, Node *_u = nullptr, Node *_v = nullptr) : depth(_d) {
        node[0] = _u;
        node[1] = _v;
    }
} city[100001];

map<pair<int, int>, Node*> mp;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> p[1].x >> p[1].y >> p[2].x >> p[2].y >> n;
    mp[{1, 2}] = new Node(1, 2);
    city[1] = city[2] = City(0, mp[{1, 2}], nullptr);

    for (int cnt = 2; n; n--) {
        char c;
        cin >> c;
        if (c == 'd') {
            cnt++;
            int a, b;
            cin >> p[cnt].x >> p[cnt].y >> a >> b;
            if (a > b) swap(a, b);
            Node *par = mp[{a, b}];

            Node *u = new Node(a, cnt);
            u->anc.push_back(par);
            u->anc_sp.push_back(SP(u, par));
            for (int i = 0; i < u->anc.size() && i < u->anc[i]->anc.size(); i++) {
                u->anc.push_back(u->anc[i]->anc[i]);
                u->anc_sp.push_back(SP(u->anc_sp[i], u->anc[i]->anc_sp[i]));
            }
            par->children.push_back(mp[{a, cnt}] = u);
            // for (SP k : u->anc_sp) {
            //     cout << u->dist << ": ";
            //     for (int i : {0, 1}) for (int j : {0, 1}) {
            //         cout << '(' << k.idx[0][i] << ' ' << k.idx[1][j] << ", " << k.cost[i][j] << ") ";
            //     }
            //     cout << endl;
            // }

            Node *v = new Node(b, cnt);
            v->anc.push_back(par);
            v->anc_sp.push_back(SP(v, par));
            for (int i = 0; i < v->anc.size() && i < v->anc[i]->anc.size(); i++) {
                v->anc.push_back(v->anc[i]->anc[i]);
                v->anc_sp.push_back(SP(v->anc_sp[i], v->anc[i]->anc_sp[i]));
            }
            par->children.push_back(mp[{b, cnt}] = v);
            // for (SP k : v->anc_sp) {
            //     cout << v->dist << ": ";
            //     for (int i : {0, 1}) for (int j : {0, 1}) {
            //         cout << '(' << k.idx[0][i] << ' ' << k.idx[1][j] << ", " << k.cost[i][j] << ") ";
            //     }
            //     cout << endl;
            // }

            city[cnt] = City(city[b].depth + 1, u, v);
        } else {
            int a, b;
            cin >> a >> b;
            if (city[a].depth < city[b].depth) swap(a, b);
            double ans = 1e18;
            // cout << "Here! " << a << ' ' << b << endl;
            for (int i : {0, 1}) for (int j : {0, 1}) if (city[a].node[i] && city[b].node[j]) {
                Node *anode = city[a].node[i], *bnode = city[b].node[j];
                SP asp = SP(anode), bsp = SP(bnode);
                for (int k = 0, diff = city[a].depth - city[b].depth; diff; k++, diff >>= 1) {
                    if (diff & 1) {
                        asp = SP(asp, anode->anc_sp[k]);
                        anode = anode->anc[k];
                    }
                }
                // cout << "Here 2!" << endl;
                for (int k = anode->anc.size() - 1; ~k; k--) {
                    if (anode->anc[k] != bnode->anc[k]) {
                        asp = SP(asp, anode->anc_sp[k]);
                        anode = anode->anc[k];
                        bsp = SP(bsp, bnode->anc_sp[k]);
                        bnode = bnode->anc[k];
                    }
                }
                // cout << asp.idx[0][0] << ' ' << asp.idx[0][1] << ' ' << asp.idx[1][0] << ' ' << asp.idx[1][1] << '\n';
                // cout << bsp.idx[0][0] << ' ' << bsp.idx[0][1] << ' ' << bsp.idx[1][0] << ' ' << bsp.idx[1][1] << '\n';

                // if (a == 3 && b == 4 && i == 0 && j == 1) {
                //     SP tmp1 = SP(asp, anode->anc_sp[0]);
                //     cout << tmp1.cost[0][0] << ' ' << tmp1.cost[0][1] << ' ' << tmp1.cost[1][0] << ' ' << tmp1.cost[1][1] << '\n';
                //     tmp1 = SP(bsp, bnode->anc_sp[0]);
                //     cout << tmp1.cost[0][0] << ' ' << tmp1.cost[0][1] << ' ' << tmp1.cost[1][0] << ' ' << tmp1.cost[1][1] << '\n';
                // }

                SP res = (anode == bnode ? SP(asp, bsp) : SP(SP(asp, anode->anc_sp[0]), SP(bsp, bnode->anc_sp[0])));
                // Take the best of res
                for (int k : {0, 1}) for (int l : {0, 1}) if (res.idx[0][k] == a && res.idx[1][l] == b)
                    ans = min(ans, res.cost[k][l]);
                // cout << "Here 3! " << ans << '\n';
            }
            cout << fixed << setprecision(6) << ans << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

grad.cpp: In function 'int main()':
grad.cpp:103:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |             for (int i = 0; i < u->anc.size() && i < u->anc[i]->anc.size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~
grad.cpp:103:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |             for (int i = 0; i < u->anc.size() && i < u->anc[i]->anc.size(); i++) {
      |                                                  ~~^~~~~~~~~~~~~~~~~~~~~~~
grad.cpp:119:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |             for (int i = 0; i < v->anc.size() && i < v->anc[i]->anc.size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~
grad.cpp:119:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |             for (int i = 0; i < v->anc.size() && i < v->anc[i]->anc.size(); i++) {
      |                                                  ~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 6
• Subtask 6: 0 / 6
• Subtask 7: 0 / 6
• Subtask 8: 0 / 11
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11
• Subtask 11: 0 / 11
• Subtask 12: 0 / 11