oj.uz

Submission #955091

# Submission time Handle Problem Language Result Execution time Memory
955091 2024-03-29T11:08:04 Z Trisanu_Das Stations (IOI20_stations) C++17
76 / 100
 596 ms 35396 KB 
#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
#include <vector>
 
#define pb push_back
#define fi first
#define se second
#define pb push_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 5e5 + 5, oo = 1e18 + 7;
 
int n;
vector<int> Adj[N];
 
int l[N], r[N], d[N];
 
vector<int> vis;
 
void dfs(int u, int p){
	vis.pb(u);
	l[u] = vis.size();
	for(auto v : Adj[u]){
		if(v == p) continue;
		d[v] = d[u] + 1;
		dfs(v, u);
		vis.pb(u);
	}
	r[u] = vis.size();
}
 
int tol[1005][1005];
ii tol2[600005];
 

 
vector<int> label(int n_, int k, vector<int> u, vector<int> v) {
	n = n_;
	vis.clear();
	for(int i = 0; i < n; i++) Adj[i].clear();
	for(int i = 0; i < (n - 1); i++){
		Adj[u[i]].pb(v[i]); Adj[v[i]].pb(u[i]);
	}
	dfs(0, 0);
	vector<int> labels(n);
	for(int i = 0; i < n; i++){
		if(!(d[i] & 1)) labels[i] = l[i];
		else labels[i] = r[i];
	}
	return labels;
}
 

 
int find_next_station(int s, int t, vector<int> c) {
	int mini = oo;
	for(auto it : c) mini = min(mini, it);
	if(mini < s){
		for(int i = 1; i < c.size(); i++){
			int le = c[i], ri;
			if(i != c.size() - 1) ri = c[i + 1] - 1;
			else ri = s;
			if(le <= t && ri >= t) return c[i];
		}
		return c[0];
	}
	else{\
		for(int i = 0; (i + 1) < c.size(); i++){
			int le = (i ? c[i - 1] + 1 : s + 1), ri = c[i];
			if(le <= t && ri >= t) return c[i];
		}
		return c.back();
	}
}

Compilation message

stations.cpp:15:34: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   15 | const int N = 5e5 + 5, oo = 1e18 + 7;
      |                             ~~~~~^~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i = 1; i < c.size(); i++){
      |                  ~~^~~~~~~~~~
stations.cpp:65:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    if(i != c.size() - 1) ri = c[i + 1] - 1;
      |       ~~^~~~~~~~~~~~~~~
stations.cpp:72:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i = 0; (i + 1) < c.size(); i++){
      |                  ~~~~~~~~^~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 34664 KB Output is correct
2 Correct 274 ms 34664 KB Output is correct
3 Correct 522 ms 32428 KB Output is correct
4 Correct 483 ms 32428 KB Output is correct
5 Correct 371 ms 30380 KB Output is correct
6 Correct 315 ms 34656 KB Output is correct
7 Correct 269 ms 34728 KB Output is correct
8 Correct 9 ms 34556 KB Output is correct
9 Correct 10 ms 34564 KB Output is correct
10 Correct 8 ms 32520 KB Output is correct
11 Correct 408 ms 34476 KB Output is correct
12 Correct 310 ms 34904 KB Output is correct
13 Correct 320 ms 34952 KB Output is correct
14 Correct 293 ms 34476 KB Output is correct
15 Correct 43 ms 34564 KB Output is correct
16 Correct 45 ms 32592 KB Output is correct
17 Correct 66 ms 30532 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 30380 KB Output is correct
2 Correct 448 ms 34476 KB Output is correct
3 Correct 344 ms 32428 KB Output is correct
4 Correct 9 ms 30484 KB Output is correct
5 Correct 10 ms 30476 KB Output is correct
6 Correct 7 ms 34560 KB Output is correct
7 Correct 388 ms 34476 KB Output is correct
8 Correct 587 ms 34664 KB Output is correct
9 Correct 465 ms 32428 KB Output is correct
10 Correct 382 ms 34476 KB Output is correct
11 Correct 11 ms 34568 KB Output is correct
12 Correct 12 ms 34564 KB Output is correct
13 Correct 9 ms 30472 KB Output is correct
14 Correct 9 ms 34560 KB Output is correct
15 Correct 7 ms 32516 KB Output is correct
16 Correct 375 ms 32428 KB Output is correct
17 Correct 337 ms 30376 KB Output is correct
18 Correct 324 ms 30380 KB Output is correct
19 Correct 411 ms 32428 KB Output is correct
20 Correct 348 ms 30380 KB Output is correct

Subtask #5
50.0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 368 ms 30584 KB Partially correct
2 Partially correct 315 ms 30572 KB Partially correct
3 Correct 596 ms 30380 KB Output is correct
4 Correct 434 ms 32428 KB Output is correct
5 Correct 390 ms 32456 KB Output is correct
6 Partially correct 307 ms 30580 KB Partially correct
7 Partially correct 290 ms 32428 KB Partially correct
8 Correct 8 ms 30476 KB Output is correct
9 Correct 10 ms 30484 KB Output is correct
10 Correct 7 ms 30560 KB Output is correct
11 Partially correct 320 ms 30532 KB Partially correct
12 Partially correct 356 ms 30496 KB Partially correct
13 Correct 590 ms 32428 KB Output is correct
14 Correct 385 ms 30660 KB Output is correct
15 Correct 406 ms 30376 KB Output is correct
16 Partially correct 307 ms 34476 KB Partially correct
17 Correct 394 ms 34476 KB Output is correct
18 Partially correct 277 ms 32848 KB Partially correct
19 Partially correct 310 ms 30872 KB Partially correct
20 Partially correct 336 ms 34476 KB Partially correct
21 Correct 45 ms 30476 KB Output is correct
22 Partially correct 49 ms 30752 KB Partially correct
23 Partially correct 68 ms 32596 KB Partially correct
24 Correct 10 ms 30476 KB Output is correct
25 Correct 9 ms 30464 KB Output is correct
26 Correct 9 ms 30472 KB Output is correct
27 Correct 10 ms 30484 KB Output is correct
28 Correct 8 ms 30480 KB Output is correct
29 Correct 409 ms 30380 KB Output is correct
30 Correct 392 ms 34476 KB Output is correct
31 Correct 348 ms 30380 KB Output is correct
32 Correct 379 ms 30380 KB Output is correct
33 Correct 347 ms 30380 KB Output is correct
34 Partially correct 207 ms 34656 KB Partially correct
35 Partially correct 301 ms 34964 KB Partially correct
36 Partially correct 295 ms 35064 KB Partially correct
37 Partially correct 266 ms 34936 KB Partially correct
38 Partially correct 325 ms 34892 KB Partially correct
39 Partially correct 280 ms 34888 KB Partially correct
40 Partially correct 293 ms 35396 KB Partially correct
41 Partially correct 292 ms 34880 KB Partially correct
42 Partially correct 40 ms 34648 KB Partially correct
43 Partially correct 64 ms 34656 KB Partially correct
44 Partially correct 90 ms 34624 KB Partially correct
45 Partially correct 101 ms 34624 KB Partially correct
46 Partially correct 181 ms 34592 KB Partially correct
47 Partially correct 184 ms 34628 KB Partially correct
48 Partially correct 45 ms 32952 KB Partially correct
49 Partially correct 38 ms 35208 KB Partially correct