oj.uz

Submission #431919

# Submission time Handle Problem Language Result Execution time Memory
431919 2021-06-17T17:17:31 Z MeGustaElArroz23 Stations (IOI20_stations) C++14
73.3608 / 100
 972 ms 816 KB 
#include "stations.h"
#include <cstdio>
#include <cassert>
#include <map>
#include <vector>
#include <algorithm>

////////
///////////////////

#include "stations.h"
#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;

int tiempo;
vvi conexiones;
vi labeles;

void bfs(int ac, int ant, bool entrada){
	
	tiempo++;
	//cerr << ac << ' ' << tiempo << '\n';
	if (entrada) labeles[ac]=tiempo;
	for (int x:conexiones[ac]){
		if (x!=ant){
			bfs(x,ac,not entrada);
		}
	}
	tiempo++;
	//cerr << ac << ' ' << tiempo << '\n';
	if (not entrada) labeles[ac]=tiempo+2000;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	//cerr<<"h";
	tiempo=-1;
	conexiones=vvi(n);
	for (int i=0;i<n-1;i++){
		conexiones[u[i]].push_back(v[i]);
		conexiones[v[i]].push_back(u[i]);
	}
	labeles=vi(n);
	bfs(0,-1, 1);
	//for (int x:labeles) cerr << x << ' ';
	//cerr<<'\n';
	return labeles;
}

int find_next_station(int ac, int obj, std::vector<int> vecinos) {
	obj%=2000;
	bool entrada=(ac<2000);
	ac%=2000;
	sort(vecinos.begin(),vecinos.end());
	if (vecinos.size()==1) return vecinos[0]; //arriba
	if (entrada){
		int izq=ac;
		if (obj<izq) return vecinos[vecinos.size()-1]; //arriba
		for (int x:vecinos){
			if (x%2000>=obj) return x; //abajo
		}
		return vecinos[vecinos.size()-1]; //arriba
	}
	else{
		int der=ac;
		if (obj>der) return vecinos[0]; //arriba
		for (int i=vecinos.size()-1;i>=0;i--){
			int x=vecinos[i];
			if (x%2000<=obj) return x; //abajo
		}
		return vecinos[0]; //arriba
	}
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 648 KB Output is correct
2 Correct 468 ms 592 KB Output is correct
3 Correct 873 ms 492 KB Output is correct
4 Correct 630 ms 488 KB Output is correct
5 Correct 582 ms 488 KB Output is correct
6 Correct 453 ms 612 KB Output is correct
7 Correct 451 ms 612 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 6 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 560 ms 480 KB Output is correct
12 Correct 502 ms 688 KB Output is correct
13 Correct 445 ms 772 KB Output is correct
14 Correct 470 ms 528 KB Output is correct
15 Correct 66 ms 544 KB Output is correct
16 Correct 64 ms 528 KB Output is correct
17 Correct 104 ms 532 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 898 ms 400 KB Output is correct
2 Correct 661 ms 400 KB Output is correct
3 Correct 636 ms 400 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 587 ms 488 KB Output is correct
8 Correct 972 ms 400 KB Output is correct
9 Correct 695 ms 400 KB Output is correct
10 Correct 613 ms 492 KB Output is correct
11 Correct 4 ms 476 KB Output is correct
12 Correct 5 ms 468 KB Output is correct
13 Correct 5 ms 476 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 2 ms 472 KB Output is correct
16 Correct 493 ms 488 KB Output is correct
17 Correct 518 ms 484 KB Output is correct
18 Correct 537 ms 400 KB Output is correct
19 Correct 542 ms 400 KB Output is correct
20 Correct 516 ms 400 KB Output is correct

Subtask #5
47.3608 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 573 ms 652 KB Partially correct
2 Partially correct 475 ms 616 KB Partially correct
3 Partially correct 859 ms 400 KB Partially correct
4 Partially correct 664 ms 400 KB Partially correct
5 Partially correct 605 ms 400 KB Partially correct
6 Partially correct 468 ms 604 KB Partially correct
7 Partially correct 474 ms 528 KB Partially correct
8 Partially correct 3 ms 468 KB Partially correct
9 Partially correct 3 ms 468 KB Partially correct
10 Partially correct 1 ms 468 KB Partially correct
11 Partially correct 446 ms 740 KB Partially correct
12 Partially correct 533 ms 528 KB Partially correct
13 Partially correct 885 ms 552 KB Partially correct
14 Partially correct 670 ms 400 KB Partially correct
15 Partially correct 626 ms 400 KB Partially correct
16 Partially correct 494 ms 492 KB Partially correct
17 Partially correct 588 ms 400 KB Partially correct
18 Partially correct 451 ms 788 KB Partially correct
19 Partially correct 494 ms 816 KB Partially correct
20 Partially correct 435 ms 484 KB Partially correct
21 Partially correct 63 ms 448 KB Partially correct
22 Partially correct 59 ms 572 KB Partially correct
23 Partially correct 110 ms 608 KB Partially correct
24 Partially correct 6 ms 468 KB Partially correct
25 Partially correct 5 ms 464 KB Partially correct
26 Partially correct 5 ms 468 KB Partially correct
27 Partially correct 3 ms 468 KB Partially correct
28 Partially correct 2 ms 468 KB Partially correct
29 Partially correct 517 ms 484 KB Partially correct
30 Partially correct 513 ms 488 KB Partially correct
31 Partially correct 496 ms 488 KB Partially correct
32 Partially correct 499 ms 400 KB Partially correct
33 Partially correct 536 ms 484 KB Partially correct
34 Partially correct 319 ms 612 KB Partially correct
35 Partially correct 421 ms 656 KB Partially correct
36 Partially correct 463 ms 776 KB Partially correct
37 Partially correct 485 ms 744 KB Partially correct
38 Partially correct 459 ms 520 KB Partially correct
39 Partially correct 411 ms 728 KB Partially correct
40 Partially correct 434 ms 696 KB Partially correct
41 Partially correct 455 ms 616 KB Partially correct
42 Partially correct 71 ms 528 KB Partially correct
43 Partially correct 99 ms 528 KB Partially correct
44 Partially correct 132 ms 528 KB Partially correct
45 Partially correct 152 ms 772 KB Partially correct
46 Partially correct 277 ms 528 KB Partially correct
47 Partially correct 306 ms 528 KB Partially correct
48 Partially correct 64 ms 624 KB Partially correct
49 Partially correct 53 ms 752 KB Partially correct