답안 #333033

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
333033 2020-12-04T09:31:27 Z dolphingarlic Grad (COI14_grad) C++14
0 / 100
503 ms 124396 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;
    }

    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);

            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);

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

                SP res = (anode == bnode ? SP(asp, bsp) : SP(SP(asp, anode->anc_sp[0]), SP(bsp, bnode->anc_sp[0])));
                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 << fixed << setprecision(6) << ans << '\n';
        }
    }
    return 0;
}

Compilation message

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: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 Incorrect 2 ms 2796 KB 5th numbers differ - expected: '30.07809', found: '38.80959', error = '8.73149'
# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 5740 KB Execution killed with signal 6 (could be triggered by violating memory limits)
# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 3436 KB 1st numbers differ - expected: '2758.49634', found: '4671.24322', error = '1912.74687'
# 결과 실행 시간 메모리 Grader output
1 Incorrect 221 ms 78444 KB 1st numbers differ - expected: '68715574.33036', found: '117075500.96292', error = '48359926.63256'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 365 ms 114924 KB 1st numbers differ - expected: '37379558.25774', found: '65133144.86504', error = '27753586.60730'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 422 ms 111468 KB 1st numbers differ - expected: '12157216.39500', found: '20788132.07374', error = '8630915.67875'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 406 ms 100972 KB 1st numbers differ - expected: '681018998.86844', found: '1189209616.33593', error = '508190617.46750'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 451 ms 111468 KB 1st numbers differ - expected: '615449.79915', found: '1051781.25823', error = '436331.45908'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 469 ms 124396 KB 4th numbers differ - expected: '9007.00783', found: '9270.68227', error = '263.67444'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 485 ms 111724 KB 1st numbers differ - expected: '4358194.66757', found: '8180461.60536', error = '3822266.93779'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 481 ms 121068 KB 5th numbers differ - expected: '733629.34687', found: '1674174.32974', error = '940544.98287'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 503 ms 113004 KB 2nd numbers differ - expected: '465.09769', found: '618.71569', error = '153.61801'
2 Halted 0 ms 0 KB -