oj.uz

Submission #816635

# Submission time Handle Problem Language Result Execution time Memory
816635 2023-08-09T05:58:28 Z tolbi Stations (IOI20_stations) C++17
100 / 100
 865 ms 764 KB 
#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& in, pair<X,Y> &pr) {return in>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> istream& operator>>(istream& in, vector<X> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X> ostream& operator<<(ostream& os, vector<X> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename X, size_t Y> istream& operator>>(istream& in, array<X,Y> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> arr) {for(auto &it : arr) os<<it<<" "; return os;}
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define INF LONG_LONG_MAX
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "stations.h"

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	vector<vector<int>> arr(n);
	vector<int> labels(n,-1);
	int ind=0;
	auto dfs = [&](int node, int lnode, bool tek, auto dfs)->void{
		ind++;
		if (tek) labels[node]=ind;
		ind++;
		for (int i = 0; i < arr[node].size(); i++){
			if (arr[node][i]==lnode) continue;
			dfs(arr[node][i],node,!tek,dfs);
		}
		ind++;
		if (!tek) labels[node]=ind;
		ind++;
	};
	for (int i = 0; i < n-1; i++){
		arr[u[i]].push_back(v[i]);
		arr[v[i]].push_back(u[i]);
	}
	dfs(0,-1,true,dfs);
	vector<pair<int,int>> sr(n);
	for (int i = 0; i < n; i++){
		sr[i]={labels[i],i};
	}
	sortarr(sr);
	for (int i = 0; i < n; i++){
		labels[sr[i].second]=i;
	}
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	if (s>c.back()){
		for (int i = c.size()-1; i >= 1; i--){
			if (t>=c[i] && t<=s){
				return c[i];
			}
		}
		return c[0];
	}
	for (int i = 0; i < c.size()-1; i++){
		if (t>=s && t<=c[i]){
			return c[i];
		}
	}
	return c.back();
}

Compilation message

stations.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i = 0; i < c.size()-1; i++){
      |                  ~~^~~~~~~~~~~~
stations.cpp: In instantiation of 'label(int, int, std::vector<int>, std::vector<int>)::<lambda(int, int, bool, auto:23)> [with auto:23 = label(int, int, std::vector<int>, std::vector<int>)::<lambda(int, int, bool, auto:23)>]':
stations.cpp:57:19:   required from here
stations.cpp:45:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 544 KB Output is correct
2 Correct 342 ms 704 KB Output is correct
3 Correct 648 ms 480 KB Output is correct
4 Correct 590 ms 420 KB Output is correct
5 Correct 438 ms 416 KB Output is correct
6 Correct 278 ms 548 KB Output is correct
7 Correct 256 ms 508 KB Output is correct
8 Correct 2 ms 420 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 552 KB Output is correct
2 Correct 404 ms 512 KB Output is correct
3 Correct 603 ms 512 KB Output is correct
4 Correct 534 ms 416 KB Output is correct
5 Correct 447 ms 572 KB Output is correct
6 Correct 295 ms 512 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 632 KB Output is correct
2 Correct 334 ms 620 KB Output is correct
3 Correct 719 ms 508 KB Output is correct
4 Correct 510 ms 508 KB Output is correct
5 Correct 408 ms 504 KB Output is correct
6 Correct 334 ms 640 KB Output is correct
7 Correct 368 ms 664 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 0 ms 500 KB Output is correct
11 Correct 385 ms 504 KB Output is correct
12 Correct 352 ms 632 KB Output is correct
13 Correct 363 ms 620 KB Output is correct
14 Correct 312 ms 544 KB Output is correct
15 Correct 42 ms 500 KB Output is correct
16 Correct 42 ms 548 KB Output is correct
17 Correct 71 ms 548 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 556 KB Output is correct
2 Correct 559 ms 508 KB Output is correct
3 Correct 515 ms 508 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 0 ms 492 KB Output is correct
7 Correct 378 ms 504 KB Output is correct
8 Correct 680 ms 512 KB Output is correct
9 Correct 410 ms 416 KB Output is correct
10 Correct 633 ms 504 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 4 ms 492 KB Output is correct
13 Correct 2 ms 492 KB Output is correct
14 Correct 2 ms 492 KB Output is correct
15 Correct 0 ms 492 KB Output is correct
16 Correct 418 ms 504 KB Output is correct
17 Correct 453 ms 504 KB Output is correct
18 Correct 448 ms 504 KB Output is correct
19 Correct 320 ms 420 KB Output is correct
20 Correct 304 ms 416 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 648 KB Output is correct
2 Correct 313 ms 552 KB Output is correct
3 Correct 865 ms 416 KB Output is correct
4 Correct 459 ms 500 KB Output is correct
5 Correct 599 ms 480 KB Output is correct
6 Correct 295 ms 624 KB Output is correct
7 Correct 307 ms 548 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 5 ms 492 KB Output is correct
10 Correct 0 ms 448 KB Output is correct
11 Correct 287 ms 504 KB Output is correct
12 Correct 471 ms 504 KB Output is correct
13 Correct 838 ms 464 KB Output is correct
14 Correct 474 ms 508 KB Output is correct
15 Correct 488 ms 476 KB Output is correct
16 Correct 353 ms 488 KB Output is correct
17 Correct 401 ms 508 KB Output is correct
18 Correct 343 ms 600 KB Output is correct
19 Correct 316 ms 624 KB Output is correct
20 Correct 366 ms 544 KB Output is correct
21 Correct 48 ms 420 KB Output is correct
22 Correct 65 ms 568 KB Output is correct
23 Correct 77 ms 636 KB Output is correct
24 Correct 4 ms 492 KB Output is correct
25 Correct 5 ms 492 KB Output is correct
26 Correct 3 ms 492 KB Output is correct
27 Correct 3 ms 492 KB Output is correct
28 Correct 1 ms 496 KB Output is correct
29 Correct 320 ms 416 KB Output is correct
30 Correct 495 ms 416 KB Output is correct
31 Correct 292 ms 512 KB Output is correct
32 Correct 446 ms 508 KB Output is correct
33 Correct 346 ms 420 KB Output is correct
34 Correct 205 ms 544 KB Output is correct
35 Correct 338 ms 644 KB Output is correct
36 Correct 413 ms 512 KB Output is correct
37 Correct 322 ms 764 KB Output is correct
38 Correct 355 ms 632 KB Output is correct
39 Correct 290 ms 688 KB Output is correct
40 Correct 326 ms 636 KB Output is correct
41 Correct 316 ms 636 KB Output is correct
42 Correct 37 ms 620 KB Output is correct
43 Correct 57 ms 572 KB Output is correct
44 Correct 71 ms 504 KB Output is correct
45 Correct 148 ms 548 KB Output is correct
46 Correct 220 ms 544 KB Output is correct
47 Correct 257 ms 548 KB Output is correct
48 Correct 48 ms 544 KB Output is correct
49 Correct 37 ms 676 KB Output is correct