oj.uz

Submission #1021221

# Submission time Handle Problem Language Result Execution time Memory
1021221 2024-07-12T15:51:38 Z kachim2 Stations (IOI20_stations) C++17
100 / 100
 1002 ms 3576 KB 
#include "stations.h"
#include <vector>
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;
int dfs(vector<int> &labels, vector<vector<int>> &tree, int v, int p, int pre, int d){
	if(d&1)
		labels[v] = pre;
	for(auto i : tree[v]){
		if(i!=p){
			pre = dfs(labels, tree, i, v, pre+1, d+1);
		}
	}
	if(!(d&1))
		labels[v] = pre;
	return pre+1;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
	vector<vector<int>> tree(n);
	for(int i = 0; i < u.size(); i++){
		tree[u[i]].push_back(v[i]);
		tree[v[i]].push_back(u[i]);
	}
	dfs(labels, tree, 0, -1, 0, 0);
	vector<pair<int, int>> labx(n);
	for(int i = 0; i < n; i++){
		labx[i] = {labels[i], i};
	}
	sort(labx.begin(), labx.end());
	for(int i = 0; i < n; i++){
		labels[labx[i].second] = i;
	}
	std::cerr << "LOG ";
	for(auto i : labels) std::cerr << i << ' ';
	std::cerr << "\n";
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {

	for(auto i : c) if(i == t) return t;
	if(c.size() == 1) return c[0]; 
	vector<int> pre(c.size()-1), post(c.size()-1);
	sort(c.begin(), c.end());
	int minn = INT_MAX, parent = 0;
	for(auto i : c) minn = min(i, minn);
	if(minn < s){
		parent = c[0];
		c.erase(c.begin());
		for(int i = 0; i < c.size(); i++) pre[i] = c[i];
		post.back() = s-1;
		for(int i = 0; i < c.size()-1; i++){
			post[i] = pre[i+1]-1;
		}
	}else{
		parent = c.back();
		c.pop_back();
		for(int i = 0; i < c.size(); i++) post[i] = c[i];
		pre[0] = s+1;
		for(int i = 1; i < c.size(); i++){
			pre[i] = post[i-1];
		}
	}
	cerr <<"S: " << s << " T: " << t << "\nPRE: ";
	for(auto i : pre) cerr << i << ' ';
	cerr << "\nPOST: ";
	for(auto i : post) cerr << i << ' ';
	cerr << '\n';
	for(int i = 0; i < c.size(); i++){
		if(t>=pre[i] && t <= post[i]) parent = c[i];
	}
	return parent;
}

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i = 0; i < u.size(); i++){
      |                 ~~^~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i = 0; i < c.size(); i++) pre[i] = c[i];
      |                  ~~^~~~~~~~~~
stations.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int i = 0; i < c.size()-1; i++){
      |                  ~~^~~~~~~~~~~~
stations.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(int i = 0; i < c.size(); i++) post[i] = c[i];
      |                  ~~^~~~~~~~~~
stations.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int i = 1; i < c.size(); i++){
      |                  ~~^~~~~~~~~~
stations.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i = 0; i < c.size(); i++){
      |                 ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 783 ms 2780 KB Output is correct
2 Correct 943 ms 2864 KB Output is correct
3 Correct 578 ms 684 KB Output is correct
4 Correct 418 ms 684 KB Output is correct
5 Correct 545 ms 1360 KB Output is correct
6 Correct 952 ms 2808 KB Output is correct
7 Correct 898 ms 2680 KB Output is correct
8 Correct 1 ms 776 KB Output is correct
9 Correct 4 ms 772 KB Output is correct
10 Correct 0 ms 776 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 2208 KB Output is correct
2 Correct 677 ms 1824 KB Output is correct
3 Correct 612 ms 684 KB Output is correct
4 Correct 448 ms 688 KB Output is correct
5 Correct 557 ms 1256 KB Output is correct
6 Correct 699 ms 2008 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 828 ms 2744 KB Output is correct
2 Correct 964 ms 3136 KB Output is correct
3 Correct 592 ms 684 KB Output is correct
4 Correct 419 ms 684 KB Output is correct
5 Correct 555 ms 1416 KB Output is correct
6 Correct 961 ms 2840 KB Output is correct
7 Correct 917 ms 2488 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 465 ms 1580 KB Output is correct
12 Correct 934 ms 2624 KB Output is correct
13 Correct 904 ms 2312 KB Output is correct
14 Correct 897 ms 2368 KB Output is correct
15 Correct 36 ms 764 KB Output is correct
16 Correct 44 ms 744 KB Output is correct
17 Correct 76 ms 744 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 684 KB Output is correct
2 Correct 471 ms 684 KB Output is correct
3 Correct 575 ms 1548 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 1 ms 776 KB Output is correct
7 Correct 476 ms 1420 KB Output is correct
8 Correct 590 ms 688 KB Output is correct
9 Correct 480 ms 684 KB Output is correct
10 Correct 575 ms 1676 KB Output is correct
11 Correct 4 ms 768 KB Output is correct
12 Correct 6 ms 776 KB Output is correct
13 Correct 4 ms 768 KB Output is correct
14 Correct 3 ms 776 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 581 ms 1744 KB Output is correct
17 Correct 588 ms 1672 KB Output is correct
18 Correct 552 ms 2012 KB Output is correct
19 Correct 551 ms 2040 KB Output is correct
20 Correct 580 ms 1468 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 807 ms 2932 KB Output is correct
2 Correct 969 ms 3320 KB Output is correct
3 Correct 613 ms 684 KB Output is correct
4 Correct 473 ms 684 KB Output is correct
5 Correct 562 ms 1556 KB Output is correct
6 Correct 1002 ms 3576 KB Output is correct
7 Correct 964 ms 2532 KB Output is correct
8 Correct 2 ms 1016 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 798 ms 2352 KB Output is correct
12 Correct 672 ms 1900 KB Output is correct
13 Correct 644 ms 684 KB Output is correct
14 Correct 466 ms 684 KB Output is correct
15 Correct 578 ms 1460 KB Output is correct
16 Correct 751 ms 2044 KB Output is correct
17 Correct 510 ms 1620 KB Output is correct
18 Correct 913 ms 2972 KB Output is correct
19 Correct 840 ms 2768 KB Output is correct
20 Correct 870 ms 2812 KB Output is correct
21 Correct 28 ms 764 KB Output is correct
22 Correct 45 ms 744 KB Output is correct
23 Correct 81 ms 892 KB Output is correct
24 Correct 4 ms 768 KB Output is correct
25 Correct 3 ms 768 KB Output is correct
26 Correct 4 ms 768 KB Output is correct
27 Correct 3 ms 768 KB Output is correct
28 Correct 2 ms 776 KB Output is correct
29 Correct 583 ms 2024 KB Output is correct
30 Correct 629 ms 1716 KB Output is correct
31 Correct 586 ms 1464 KB Output is correct
32 Correct 576 ms 1388 KB Output is correct
33 Correct 579 ms 1916 KB Output is correct
34 Correct 656 ms 2280 KB Output is correct
35 Correct 759 ms 2544 KB Output is correct
36 Correct 842 ms 2828 KB Output is correct
37 Correct 695 ms 2408 KB Output is correct
38 Correct 695 ms 1852 KB Output is correct
39 Correct 704 ms 1696 KB Output is correct
40 Correct 724 ms 2140 KB Output is correct
41 Correct 706 ms 2184 KB Output is correct
42 Correct 47 ms 744 KB Output is correct
43 Correct 80 ms 688 KB Output is correct
44 Correct 558 ms 1944 KB Output is correct
45 Correct 625 ms 2004 KB Output is correct
46 Correct 735 ms 2500 KB Output is correct
47 Correct 802 ms 2380 KB Output is correct
48 Correct 446 ms 1336 KB Output is correct
49 Correct 378 ms 1712 KB Output is correct