답안 #333059

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
333059 2020-12-04T11:50:48 Z dolphingarlic Grad (COI14_grad) C++14
14 / 100
485 ms 121068 KB
#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;
    }

    Node *complement;
    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->complement->dist;
        } else {
            cost[0][0] = v->dist;
            cost[0][1] = 0;
            cost[1][0] = u->complement->dist;
            cost[1][1] = u->dist;
        }
    }

    SP(SP a, SP b) {
        if (a.idx[1][0] == b.idx[0][1] && a.idx[1][1] == b.idx[0][0]) {
            swap(a.idx[1][0], a.idx[1][1]);
            swap(a.cost[0][0], a.cost[0][1]);
            swap(a.cost[1][0], a.cost[1][1]);
        }
        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), *v = new Node(b, cnt);
            u->complement = v, v->complement = u;

            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;

            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];
                    }
                }

                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]);
                if (anode != bnode) {
                    asp = SP(asp, anode->anc_sp[0]), bsp = SP(bsp, bnode->anc_sp[0]);
                    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

grad.cpp: In function 'int main()':
grad.cpp:104:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for (int i = 0; i < u->anc.size() && i < u->anc[i]->anc.size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~
grad.cpp:104:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for (int i = 0; i < u->anc.size() && i < u->anc[i]->anc.size(); i++) {
      |                                                  ~~^~~~~~~~~~~~~~~~~~~~~~~
grad.cpp:112:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             for (int i = 0; i < v->anc.size() && i < v->anc[i]->anc.size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~
grad.cpp:112:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             for (int i = 0; i < v->anc.size() && i < v->anc[i]->anc.size(); i++) {
      |                                                  ~~^~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2796 KB 41 numbers
# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 5740 KB Execution killed with signal 6 (could be triggered by violating memory limits)
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3436 KB 500 numbers
# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 76268 KB 15000 numbers
2 Runtime error 97 ms 53248 KB Execution killed with signal 6 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 364 ms 111540 KB 28333 numbers
2 Runtime error 167 ms 102508 KB Execution killed with signal 6 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 404 ms 108524 KB 50000 numbers
2 Runtime error 281 ms 112176 KB Execution killed with signal 6 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 406 ms 98156 KB 55000 numbers
2 Runtime error 190 ms 107884 KB Execution killed with signal 6 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 456 ms 108468 KB 50000 numbers
2 Correct 456 ms 107604 KB 50000 numbers
3 Runtime error 290 ms 88044 KB Execution killed with signal 6 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 485 ms 121068 KB 44000 numbers
2 Correct 460 ms 118252 KB 44000 numbers
3 Runtime error 7 ms 5868 KB Execution killed with signal 6 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 473 ms 108524 KB 50000 numbers
2 Correct 460 ms 108396 KB 50000 numbers
3 Runtime error 95 ms 37996 KB Execution killed with signal 6 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 477 ms 117484 KB 45713 numbers
2 Correct 481 ms 99308 KB 54285 numbers
3 Runtime error 37 ms 16364 KB Execution killed with signal 6 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 461 ms 109932 KB 49285 numbers
2 Correct 468 ms 109932 KB 49285 numbers
3 Runtime error 18 ms 9964 KB Execution killed with signal 6 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -