oj.uz

Submission #592305

# Submission time Handle Problem Language Result Execution time Memory
592305 2022-07-08T22:26:00 Z farhan132 Stations (IOI20_stations) C++17
100 / 100
 947 ms 896 KB 
#include "stations.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back
#define in insert
 
const ll N = 1005;
vector < ll > v[N];
vector < int > labels;
 
ll in[N], out[N];
ll tim = 0;
 
void dfs(ll s, ll p = -1, ll d = 1){
	if(d%2 == 1) in[s] = tim++;
	for(auto u : v[s]){
		if(u - p){
			dfs(u, s, d + 1);
		}
	}
	if(d%2 == 0) out[s] = tim++;
	if(d&1) labels[s] = (in[s]);
	else labels[s] = (out[s]);
}
 
std::vector<int> label(int n, int k, std::vector<int> U, std::vector<int> V) {
 
	for(ll i = 0; i < n; i++) v[i].clear();
	labels.resize(0); tim = 0;
	
	for(ll i = 0; i < n - 1; i++){
		ll x = U[i], y = V[i];
		v[x].pb(y);
		v[y].pb(x);
	}
	labels.resize(n);
	set < ll > s;


 
	dfs(0);

	for(ll i = 0; i < n; i++){
		s.in(labels[i]);
	}
	assert(s.size() == n);
 
 
	//for(auto u : labels) cout << u << ' ';
	//cout << '\n';
 
	return labels;
}
 
int find_next_station(int s, int t, std::vector<int> c) {
	if(c.size() == 1){
		return c[0];
	}
	//s = (s * 2) + 1;
	//t = (t * 2) + 1;
	for(ll i = 0; i < c.size(); i++){
		//c[i] = (c[i] * 2) + 1;
	}
	if(s == 0){
		for(ll i = 0; i < c.size(); i++){
			if(t <= c[i]) return c[i];
		}
	}
	bool f = 1;
	for(auto u : c){
		if(u < s) f = 0;
	}
	if(f){
		// s is IN
		ll par = c.back(); c.pop_back();
		c.emplace(c.begin(), s);
		for(ll i = 1; i < c.size(); i++){
			if(c[i - 1] < t && t <= c[i]) return (c[i]);
		}
		return (par);
	}
	// s is OUT
	ll par = c[0];
	c.pb(s);
	for(ll i = 2; i < c.size(); i++){
		if(c[i - 1] <= t && t < c[i]) return (c[i - 1]);
	}
	return (par);
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from stations.cpp:2:
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:53:18: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |  assert(s.size() == n);
      |         ~~~~~~~~~^~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:68:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(ll i = 0; i < c.size(); i++){
      |                ~~^~~~~~~~~~
stations.cpp:72:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(ll i = 0; i < c.size(); i++){
      |                 ~~^~~~~~~~~~
stations.cpp:84:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for(ll i = 1; i < c.size(); i++){
      |                 ~~^~~~~~~~~~
stations.cpp:92:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(ll i = 2; i < c.size(); i++){
      |                ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 672 KB Output is correct
2 Correct 348 ms 716 KB Output is correct
3 Correct 775 ms 484 KB Output is correct
4 Correct 764 ms 420 KB Output is correct
5 Correct 647 ms 536 KB Output is correct
6 Correct 480 ms 652 KB Output is correct
7 Correct 444 ms 676 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 1 ms 504 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 532 KB Output is correct
2 Correct 446 ms 544 KB Output is correct
3 Correct 947 ms 544 KB Output is correct
4 Correct 574 ms 540 KB Output is correct
5 Correct 628 ms 528 KB Output is correct
6 Correct 475 ms 544 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 672 KB Output is correct
2 Correct 452 ms 676 KB Output is correct
3 Correct 858 ms 416 KB Output is correct
4 Correct 667 ms 484 KB Output is correct
5 Correct 603 ms 420 KB Output is correct
6 Correct 383 ms 660 KB Output is correct
7 Correct 467 ms 672 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 0 ms 620 KB Output is correct
11 Correct 632 ms 528 KB Output is correct
12 Correct 423 ms 672 KB Output is correct
13 Correct 484 ms 780 KB Output is correct
14 Correct 453 ms 532 KB Output is correct
15 Correct 44 ms 608 KB Output is correct
16 Correct 49 ms 736 KB Output is correct
17 Correct 132 ms 672 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 692 ms 656 KB Output is correct
2 Correct 690 ms 600 KB Output is correct
3 Correct 653 ms 416 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 0 ms 500 KB Output is correct
7 Correct 485 ms 536 KB Output is correct
8 Correct 854 ms 420 KB Output is correct
9 Correct 650 ms 416 KB Output is correct
10 Correct 471 ms 416 KB Output is correct
11 Correct 4 ms 492 KB Output is correct
12 Correct 5 ms 620 KB Output is correct
13 Correct 5 ms 492 KB Output is correct
14 Correct 3 ms 492 KB Output is correct
15 Correct 1 ms 500 KB Output is correct
16 Correct 474 ms 536 KB Output is correct
17 Correct 439 ms 536 KB Output is correct
18 Correct 486 ms 528 KB Output is correct
19 Correct 436 ms 416 KB Output is correct
20 Correct 495 ms 548 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 672 KB Output is correct
2 Correct 492 ms 672 KB Output is correct
3 Correct 875 ms 416 KB Output is correct
4 Correct 559 ms 548 KB Output is correct
5 Correct 566 ms 532 KB Output is correct
6 Correct 506 ms 700 KB Output is correct
7 Correct 441 ms 660 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 3 ms 500 KB Output is correct
10 Correct 0 ms 500 KB Output is correct
11 Correct 463 ms 544 KB Output is correct
12 Correct 501 ms 548 KB Output is correct
13 Correct 851 ms 416 KB Output is correct
14 Correct 504 ms 536 KB Output is correct
15 Correct 469 ms 544 KB Output is correct
16 Correct 424 ms 532 KB Output is correct
17 Correct 591 ms 528 KB Output is correct
18 Correct 433 ms 780 KB Output is correct
19 Correct 470 ms 784 KB Output is correct
20 Correct 485 ms 536 KB Output is correct
21 Correct 49 ms 600 KB Output is correct
22 Correct 78 ms 676 KB Output is correct
23 Correct 133 ms 672 KB Output is correct
24 Correct 3 ms 492 KB Output is correct
25 Correct 5 ms 628 KB Output is correct
26 Correct 5 ms 492 KB Output is correct
27 Correct 4 ms 492 KB Output is correct
28 Correct 2 ms 492 KB Output is correct
29 Correct 461 ms 544 KB Output is correct
30 Correct 557 ms 612 KB Output is correct
31 Correct 433 ms 416 KB Output is correct
32 Correct 468 ms 532 KB Output is correct
33 Correct 555 ms 468 KB Output is correct
34 Correct 329 ms 672 KB Output is correct
35 Correct 398 ms 792 KB Output is correct
36 Correct 410 ms 672 KB Output is correct
37 Correct 371 ms 776 KB Output is correct
38 Correct 461 ms 784 KB Output is correct
39 Correct 420 ms 896 KB Output is correct
40 Correct 303 ms 748 KB Output is correct
41 Correct 467 ms 772 KB Output is correct
42 Correct 46 ms 672 KB Output is correct
43 Correct 106 ms 660 KB Output is correct
44 Correct 123 ms 548 KB Output is correct
45 Correct 187 ms 676 KB Output is correct
46 Correct 276 ms 544 KB Output is correct
47 Correct 239 ms 676 KB Output is correct
48 Correct 59 ms 844 KB Output is correct
49 Correct 74 ms 884 KB Output is correct