| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 333030 |
2020-12-04T09:29:24 Z |
dolphingarlic |
Grad (COI14_grad) |
C++14 |
|
493 ms |
126316 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);
// 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
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++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2924 KB |
5th numbers differ - expected: '30.07809', found: '38.80959', error = '8.73149' |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
5740 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3564 KB |
1st numbers differ - expected: '2758.49634', found: '4671.24322', error = '1912.74687' |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
231 ms |
79532 KB |
1st numbers differ - expected: '68715574.33036', found: '117075500.96292', error = '48359926.63256' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
416 ms |
116504 KB |
1st numbers differ - expected: '37379558.25774', found: '65133144.86504', error = '27753586.60730' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
424 ms |
113516 KB |
1st numbers differ - expected: '12157216.39500', found: '20788132.07374', error = '8630915.67875' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
413 ms |
102768 KB |
1st numbers differ - expected: '681018998.86844', found: '1189209616.33593', error = '508190617.46750' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
458 ms |
113520 KB |
1st numbers differ - expected: '615449.79915', found: '1051781.25823', error = '436331.45908' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
480 ms |
126316 KB |
4th numbers differ - expected: '9007.00783', found: '9270.68227', error = '263.67444' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
460 ms |
113388 KB |
1st numbers differ - expected: '4358194.66757', found: '8180461.60536', error = '3822266.93779' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
493 ms |
123124 KB |
5th numbers differ - expected: '733629.34687', found: '1674174.32974', error = '940544.98287' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
472 ms |
114796 KB |
2nd numbers differ - expected: '465.09769', found: '618.71569', error = '153.61801' |
| 2 |
Halted |
0 ms |
0 KB |
- |
