oj.uz

Submission #432025

# Submission time Handle Problem Language Result Execution time Memory
432025 2021-06-17T19:12:42 Z MeGustaElArroz23 Stations (IOI20_stations) C++14
76 / 100
 930 ms 824 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){
	if (entrada) tiempo++;
	//cerr << ac << ' ' << tiempo << '\n';
	if (entrada) labeles[ac]=tiempo;
	for (int x:conexiones[ac]){
		if (x!=ant){
			bfs(x,ac,not entrada);
		}
	}
	if (not entrada) tiempo++;
	//cerr << ac << ' ' << tiempo << '\n';
	if (not entrada) labeles[ac]=tiempo+1000;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	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%=1000;
	bool entrada=(ac<1000);
	ac%=1000;
	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%1000>=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%1000<=obj) return x; //abajo
		}
		return vecinos[0]; //arriba
	}
}





////////

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 700 KB Output is correct
2 Correct 417 ms 608 KB Output is correct
3 Correct 851 ms 528 KB Output is correct
4 Correct 625 ms 400 KB Output is correct
5 Correct 563 ms 476 KB Output is correct
6 Correct 454 ms 604 KB Output is correct
7 Correct 466 ms 624 KB Output is correct
8 Correct 2 ms 476 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 618 ms 400 KB Output is correct
12 Correct 464 ms 688 KB Output is correct
13 Correct 443 ms 600 KB Output is correct
14 Correct 437 ms 528 KB Output is correct
15 Correct 59 ms 480 KB Output is correct
16 Correct 65 ms 528 KB Output is correct
17 Correct 100 ms 528 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 930 ms 472 KB Output is correct
2 Correct 712 ms 464 KB Output is correct
3 Correct 717 ms 400 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 579 ms 484 KB Output is correct
8 Correct 828 ms 400 KB Output is correct
9 Correct 627 ms 400 KB Output is correct
10 Correct 616 ms 400 KB Output is correct
11 Correct 6 ms 468 KB Output is correct
12 Correct 6 ms 468 KB Output is correct
13 Correct 5 ms 468 KB Output is correct
14 Correct 4 ms 476 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 557 ms 488 KB Output is correct
17 Correct 506 ms 400 KB Output is correct
18 Correct 513 ms 400 KB Output is correct
19 Correct 517 ms 484 KB Output is correct
20 Correct 532 ms 484 KB Output is correct

Subtask #5
50.0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 530 ms 652 KB Partially correct
2 Partially correct 407 ms 672 KB Partially correct
3 Partially correct 916 ms 400 KB Partially correct
4 Partially correct 737 ms 488 KB Partially correct
5 Partially correct 626 ms 484 KB Partially correct
6 Partially correct 452 ms 612 KB Partially correct
7 Partially correct 455 ms 488 KB Partially correct
8 Partially correct 3 ms 468 KB Partially correct
9 Partially correct 5 ms 464 KB Partially correct
10 Partially correct 2 ms 476 KB Partially correct
11 Partially correct 469 ms 616 KB Partially correct
12 Partially correct 518 ms 488 KB Partially correct
13 Partially correct 848 ms 484 KB Partially correct
14 Partially correct 667 ms 484 KB Partially correct
15 Partially correct 577 ms 400 KB Partially correct
16 Partially correct 472 ms 484 KB Partially correct
17 Partially correct 581 ms 400 KB Partially correct
18 Partially correct 406 ms 676 KB Partially correct
19 Partially correct 472 ms 720 KB Partially correct
20 Partially correct 422 ms 528 KB Partially correct
21 Partially correct 57 ms 476 KB Partially correct
22 Partially correct 73 ms 576 KB Partially correct
23 Partially correct 108 ms 548 KB Partially correct
24 Partially correct 5 ms 468 KB Partially correct
25 Partially correct 6 ms 468 KB Partially correct
26 Partially correct 5 ms 468 KB Partially correct
27 Partially correct 4 ms 476 KB Partially correct
28 Partially correct 2 ms 476 KB Partially correct
29 Partially correct 493 ms 488 KB Partially correct
30 Partially correct 491 ms 528 KB Partially correct
31 Partially correct 471 ms 488 KB Partially correct
32 Partially correct 496 ms 532 KB Partially correct
33 Partially correct 470 ms 400 KB Partially correct
34 Partially correct 289 ms 692 KB Partially correct
35 Partially correct 430 ms 652 KB Partially correct
36 Partially correct 420 ms 720 KB Partially correct
37 Partially correct 446 ms 676 KB Partially correct
38 Partially correct 482 ms 588 KB Partially correct
39 Partially correct 443 ms 824 KB Partially correct
40 Partially correct 412 ms 712 KB Partially correct
41 Partially correct 473 ms 812 KB Partially correct
42 Partially correct 63 ms 576 KB Partially correct
43 Partially correct 109 ms 528 KB Partially correct
44 Partially correct 143 ms 528 KB Partially correct
45 Partially correct 178 ms 620 KB Partially correct
46 Partially correct 319 ms 528 KB Partially correct
47 Partially correct 289 ms 696 KB Partially correct
48 Partially correct 63 ms 636 KB Partially correct
49 Partially correct 63 ms 540 KB Partially correct