oj.uz

Submission #399069

# Submission time Handle Problem Language Result Execution time Memory
399069 2021-05-05T08:46:06 Z Antekb Stations (IOI20_stations) C++14
76 / 100
 1202 ms 804 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int pre[N], post[N], d[N];
vector<int> E[N];
int wsk=1;
void dfs(int v, int p){
	//cout<<v<<" "<<p<<" "<<wsk<<endl;
	pre[v]=wsk++;
	for(int u:E[v]){
		if(u!=p){
			assert(pre[u]==0);
			d[u]=d[v]+1;
			dfs(u, v);
		}
	}
	post[v]=wsk++;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	for(int i=0; i<n; i++){
		pre[i]=post[i]=d[i]=0;
		E[i].clear();
	}
	for(int i=0; i<n-1; i++){
		E[u[i]].push_back(v[i]);
		E[v[i]].push_back(u[i]);
	}
	std::vector<int> labels(n);
	wsk=1;
	d[0]=0;
	dfs(0, -1);
	for (int i = 0; i < n; i++) {
		if(d[i]&1)labels[i] = pre[i];
		else labels[i]=post[i];
		//cout<<i<<" "<<labels[i]<<"\n";
	}
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	sort(c.begin(), c.end());
	bool ma=1;
	for(int i:c){
		if(i>s)ma=0;
	}
	if(ma){
		if(t>=s)return c[0];
		for(int i=c.size()-1; i>=0; i--){
			if(c[i]<=t)return c[i];
		}
		return c[0];
	}
	else{
		//reverse(c.begin(), c.end());
		if(t<s)return c.back();
		for(int i=0; i<c.size(); i++){
			if(c[i]>=t)return c[i];
		}
		return c.back();
	}
}

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 733 ms 624 KB Output is correct
2 Correct 591 ms 652 KB Output is correct
3 Correct 1109 ms 504 KB Output is correct
4 Correct 739 ms 400 KB Output is correct
5 Correct 811 ms 500 KB Output is correct
6 Correct 563 ms 528 KB Output is correct
7 Correct 560 ms 592 KB Output is correct
8 Correct 3 ms 728 KB Output is correct
9 Correct 5 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 626 ms 508 KB Output is correct
12 Correct 433 ms 772 KB Output is correct
13 Correct 548 ms 528 KB Output is correct
14 Correct 635 ms 632 KB Output is correct
15 Correct 72 ms 584 KB Output is correct
16 Correct 66 ms 580 KB Output is correct
17 Correct 115 ms 656 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1138 ms 504 KB Output is correct
2 Correct 763 ms 528 KB Output is correct
3 Correct 809 ms 784 KB Output is correct
4 Correct 3 ms 728 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 2 ms 476 KB Output is correct
7 Correct 740 ms 528 KB Output is correct
8 Correct 1014 ms 492 KB Output is correct
9 Correct 889 ms 512 KB Output is correct
10 Correct 626 ms 400 KB Output is correct
11 Correct 7 ms 608 KB Output is correct
12 Correct 7 ms 728 KB Output is correct
13 Correct 6 ms 600 KB Output is correct
14 Correct 4 ms 596 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 641 ms 528 KB Output is correct
17 Correct 591 ms 516 KB Output is correct
18 Correct 712 ms 400 KB Output is correct
19 Correct 669 ms 528 KB Output is correct
20 Correct 574 ms 544 KB Output is correct

Subtask #5
50.0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 718 ms 660 KB Partially correct
2 Partially correct 513 ms 620 KB Partially correct
3 Correct 1202 ms 508 KB Output is correct
4 Correct 710 ms 512 KB Output is correct
5 Correct 662 ms 400 KB Output is correct
6 Partially correct 593 ms 628 KB Partially correct
7 Partially correct 444 ms 528 KB Partially correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 5 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Partially correct 510 ms 492 KB Partially correct
12 Partially correct 724 ms 528 KB Partially correct
13 Correct 939 ms 500 KB Output is correct
14 Correct 780 ms 528 KB Output is correct
15 Correct 677 ms 512 KB Output is correct
16 Partially correct 549 ms 492 KB Partially correct
17 Correct 605 ms 520 KB Output is correct
18 Partially correct 518 ms 628 KB Partially correct
19 Partially correct 489 ms 764 KB Partially correct
20 Partially correct 554 ms 528 KB Partially correct
21 Correct 57 ms 572 KB Output is correct
22 Partially correct 67 ms 656 KB Partially correct
23 Partially correct 144 ms 660 KB Partially correct
24 Correct 6 ms 468 KB Output is correct
25 Correct 5 ms 600 KB Output is correct
26 Correct 4 ms 580 KB Output is correct
27 Correct 5 ms 484 KB Output is correct
28 Correct 2 ms 600 KB Output is correct
29 Correct 724 ms 536 KB Output is correct
30 Correct 694 ms 568 KB Output is correct
31 Correct 513 ms 528 KB Output is correct
32 Correct 513 ms 520 KB Output is correct
33 Correct 724 ms 500 KB Output is correct
34 Partially correct 433 ms 656 KB Partially correct
35 Partially correct 613 ms 740 KB Partially correct
36 Partially correct 412 ms 616 KB Partially correct
37 Partially correct 613 ms 804 KB Partially correct
38 Partially correct 454 ms 640 KB Partially correct
39 Partially correct 654 ms 740 KB Partially correct
40 Partially correct 525 ms 736 KB Partially correct
41 Partially correct 540 ms 644 KB Partially correct
42 Partially correct 78 ms 680 KB Partially correct
43 Partially correct 131 ms 668 KB Partially correct
44 Partially correct 184 ms 520 KB Partially correct
45 Partially correct 190 ms 600 KB Partially correct
46 Partially correct 383 ms 528 KB Partially correct
47 Partially correct 301 ms 652 KB Partially correct
48 Partially correct 64 ms 712 KB Partially correct
49 Partially correct 70 ms 788 KB Partially correct