oj.uz

Submission #333073

# Submission time Handle Problem Language Result Execution time Memory
333073 2020-12-04T12:08:00 Z dolphingarlic Grad (COI14_grad) C++14
100 / 100
 414 ms 121196 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) {
		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(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;
			Node *anode = city[a].node[0], *bnode = city[b].node[0];
			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 (k < anode->anc.size() && 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:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |    for (int i = 0; i < u->anc.size() && i < u->anc[i]->anc.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~
grad.cpp:94:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |    for (int i = 0; i < u->anc.size() && i < u->anc[i]->anc.size(); i++) {
      |                                         ~~^~~~~~~~~~~~~~~~~~~~~~~
grad.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |    for (int i = 0; i < v->anc.size() && i < v->anc[i]->anc.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~
grad.cpp:102:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |    for (int i = 0; i < v->anc.size() && i < v->anc[i]->anc.size(); i++) {
      |                                         ~~^~~~~~~~~~~~~~~~~~~~~~~
grad.cpp:123:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     if (k < anode->anc.size() && anode->anc[k] != bnode->anc[k]) {
      |         ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB 41 numbers

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2924 KB 300 numbers

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3436 KB 500 numbers

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 76396 KB 15000 numbers
2 Correct 141 ms 44908 KB 15000 numbers
3 Correct 188 ms 65900 KB 30000 numbers

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 111596 KB 28333 numbers
2 Correct 257 ms 96620 KB 28333 numbers
3 Correct 361 ms 87404 KB 40000 numbers

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 108516 KB 50000 numbers
2 Correct 282 ms 56556 KB 50000 numbers
3 Correct 334 ms 108612 KB 50000 numbers

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 98156 KB 55000 numbers
2 Correct 287 ms 86124 KB 55000 numbers
3 Correct 329 ms 108652 KB 50000 numbers

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 108524 KB 50000 numbers
2 Correct 345 ms 107628 KB 50000 numbers
3 Correct 302 ms 44524 KB 50000 numbers
4 Correct 382 ms 108652 KB 50000 numbers

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 121096 KB 44000 numbers
2 Correct 348 ms 118380 KB 44000 numbers
3 Correct 301 ms 67820 KB 44000 numbers
4 Correct 391 ms 121196 KB 44000 numbers

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 108524 KB 50000 numbers
2 Correct 369 ms 108396 KB 50000 numbers
3 Correct 306 ms 49516 KB 50000 numbers
4 Correct 383 ms 108652 KB 50000 numbers

Subtask #11
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 117612 KB 45713 numbers
2 Correct 362 ms 99308 KB 54285 numbers
3 Correct 290 ms 45420 KB 58571 numbers
4 Correct 372 ms 94060 KB 57000 numbers

Subtask #12
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 109932 KB 49285 numbers
2 Correct 385 ms 109932 KB 49285 numbers
3 Correct 342 ms 49132 KB 49285 numbers
4 Correct 392 ms 118892 KB 45000 numbers