oj.uz

Submission #432788

# Submission time Handle Problem Language Result Execution time Memory
432788 2021-06-18T13:22:07 Z Hazem Stations (IOI20_stations) C++14
52.3205 / 100
 955 ms 796 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

const int N = 2e3;
int cnt = 0;

int dfs(int i,int pre,vector<int> &ret,vector<int> adj[]){

	int mx = cnt;
	ret[i] = cnt++;
	
	for(int j=0;j<adj[i].size();j++){
		int v = adj[i][j];
		if(v==pre)continue;

		mx = max(mx,dfs(v,i,ret,adj));
	}
	ret[i] += mx*1000;
	return mx;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	
	cnt = 0;
	vector<int>adj[N];
	for(int i=0;i<n-1;i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	vector<int> ret = vector<int>(n,0);
	dfs(0,0,ret,adj);
	return ret;
}

int get_val(int x,int l,int r){

	int ret = 0;
	return x%1000;
	for(int i=l;i<=r;i++)
		ret |= (1<<(i-l))*(((1<<i)&x)>0);
	return ret;
}

bool cmp(int x,int y){

	return get_val(x,0,9)<get_val(y,0,9);
}

int find_next_station(int s, int t, std::vector<int> c) {
	
	int s1 = get_val(s,0,9);	int t1 = get_val(t,0,9);	
	sort(c.begin(),c.end(),cmp);
	
	if(t1<s1)
		return c[0];

	vector<int>vec;
	for(int i=1;i<c.size();i++)
		vec.push_back(get_val(c[i],0,9));

	vec.push_back(c.back()/1000+1);
	for(int i=0;i<(int)vec.size()-1;i++)
		if(t1>=vec[i]&&t1<vec[i+1])
			return c[i+1];
	return c[0];
}

Compilation message

stations.cpp: In function 'int dfs(int, int, std::vector<int>&, std::vector<int>*)':
stations.cpp:15:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for(int j=0;j<adj[i].size();j++){
      |              ~^~~~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i=1;i<c.size();i++)
      |              ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 412 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=9000
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 268 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=995000
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 596 KB Output is correct
2 Correct 495 ms 616 KB Output is correct
3 Correct 873 ms 480 KB Output is correct
4 Correct 611 ms 480 KB Output is correct
5 Correct 562 ms 400 KB Output is correct
6 Correct 490 ms 616 KB Output is correct
7 Correct 474 ms 616 KB Output is correct
8 Correct 3 ms 548 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 599 ms 656 KB Output is correct
12 Correct 460 ms 796 KB Output is correct
13 Correct 513 ms 600 KB Output is correct
14 Correct 423 ms 528 KB Output is correct
15 Correct 67 ms 576 KB Output is correct
16 Correct 80 ms 528 KB Output is correct
17 Correct 112 ms 696 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 937 ms 480 KB Output is correct
2 Correct 635 ms 496 KB Output is correct
3 Correct 603 ms 528 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 610 ms 468 KB Output is correct
8 Correct 896 ms 476 KB Output is correct
9 Correct 682 ms 528 KB Output is correct
10 Correct 555 ms 492 KB Output is correct
11 Correct 7 ms 596 KB Output is correct
12 Correct 6 ms 592 KB Output is correct
13 Correct 5 ms 596 KB Output is correct
14 Correct 4 ms 604 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 532 ms 528 KB Output is correct
17 Correct 506 ms 528 KB Output is correct
18 Correct 538 ms 484 KB Output is correct
19 Correct 551 ms 532 KB Output is correct
20 Correct 534 ms 604 KB Output is correct

Subtask #5
26.3205 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 536 ms 612 KB Partially correct
2 Partially correct 462 ms 528 KB Partially correct
3 Partially correct 941 ms 540 KB Partially correct
4 Partially correct 660 ms 476 KB Partially correct
5 Partially correct 584 ms 484 KB Partially correct
6 Partially correct 467 ms 656 KB Partially correct
7 Partially correct 460 ms 528 KB Partially correct
8 Partially correct 3 ms 648 KB Partially correct
9 Partially correct 5 ms 596 KB Partially correct
10 Partially correct 2 ms 596 KB Partially correct
11 Partially correct 502 ms 528 KB Partially correct
12 Partially correct 544 ms 484 KB Partially correct
13 Partially correct 955 ms 480 KB Partially correct
14 Partially correct 712 ms 464 KB Partially correct
15 Partially correct 698 ms 592 KB Partially correct
16 Partially correct 589 ms 548 KB Partially correct
17 Partially correct 574 ms 492 KB Partially correct
18 Partially correct 447 ms 700 KB Partially correct
19 Partially correct 516 ms 732 KB Partially correct
20 Partially correct 489 ms 484 KB Partially correct
21 Partially correct 63 ms 528 KB Partially correct
22 Partially correct 78 ms 552 KB Partially correct
23 Partially correct 101 ms 528 KB Partially correct
24 Partially correct 5 ms 600 KB Partially correct
25 Partially correct 5 ms 596 KB Partially correct
26 Partially correct 5 ms 596 KB Partially correct
27 Partially correct 5 ms 596 KB Partially correct
28 Partially correct 2 ms 596 KB Partially correct
29 Partially correct 491 ms 484 KB Partially correct
30 Partially correct 510 ms 488 KB Partially correct
31 Partially correct 550 ms 528 KB Partially correct
32 Partially correct 535 ms 488 KB Partially correct
33 Partially correct 552 ms 476 KB Partially correct
34 Partially correct 342 ms 620 KB Partially correct
35 Partially correct 465 ms 660 KB Partially correct
36 Partially correct 475 ms 736 KB Partially correct
37 Partially correct 478 ms 628 KB Partially correct
38 Partially correct 462 ms 564 KB Partially correct
39 Partially correct 462 ms 684 KB Partially correct
40 Partially correct 452 ms 696 KB Partially correct
41 Partially correct 452 ms 596 KB Partially correct
42 Partially correct 68 ms 528 KB Partially correct
43 Partially correct 128 ms 528 KB Partially correct
44 Partially correct 137 ms 588 KB Partially correct
45 Partially correct 160 ms 600 KB Partially correct
46 Partially correct 322 ms 528 KB Partially correct
47 Partially correct 332 ms 748 KB Partially correct
48 Partially correct 71 ms 528 KB Partially correct
49 Partially correct 72 ms 640 KB Partially correct