Submission #333042

#	Time	Username	Problem	Language	Result	Execution time	Memory
333042		dolphingarlic	Grad (COI14_grad)	C++14	0 / 100	495 ms	121068 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 *> 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]));
            }
            mp[{a, cnt}] = u;

            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]));
            }
            mp[{b, cnt}] = v;

            city[cnt] = City(max(city[a].depth, 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;
            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];
                    }
                }
                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];
                    }
                }

                // if (a == 11 && b == 8 && i == 0 && j == 1) {
                //     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';
                // }

                for (int k : {0, 1}) for (int l : {0, 1}) if (asp.idx[0][k] == a && bsp.idx[0][l] == b)
                    for (int m : {0, 1}) for (int o : {0, 1}) if (asp.idx[1][m] == bsp.idx[1][o])
                        ans = min(ans, asp.cost[k][m] + bsp.cost[l][o]);
            }
            cout << fixed << setprecision(6) << ans << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

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