oj.uz

Submission #872193

# Submission time Handle Problem Language Result Execution time Memory
872193 2023-11-12T13:22:39 Z kitkat12 Stations (IOI20_stations) C++14
52.3205 / 100
 524 ms 1652 KB 
#include <bits/stdc++.h>
#include <typeinfo>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define debug(x) std::cout << #x << ": " << x << "\n"
//#define all(v) v.begin(), v.end()
#define LPRINT(a, b) for (auto&(a) : (b))
#define li(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define lij(i,a,b) for (int (i) = (a); (i) <= (b); (i)++)
#define endl '\n'
#define mem(name,val) memset(name,val,sizeof(name))

//#define mod 1000000007
#define mod 998244353

vector<int> adj[1001];
bool visited[1001];
int timer = 0;
int m = 1000;
int dtime[1001], ftime[1001];

void dfs(int start){

	visited[start] = 1;
	dtime[start] = ++timer;

	for(int neigh : adj[start]){
		if(!visited[neigh]){
			dfs(neigh);
		}
	}

	ftime[start] = timer; 
}

vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
	vector<int> labels(n,0);
	for(int i=0;i<n;i++){
		adj[i].clear();	
		visited[i] = 0;
	} 

	for(int i = 0; i<u.size(); i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}

	timer = -1;

	dfs(0);

	for(int i = 0; i<n; i++){
		labels[i] = m * dtime[i] + ftime[i];
	}

	return labels;
}

int find_next_station(int s, int t, vector<int> c)
{
	int l1 = s/m, r1 = s%m;
	int l2 = t/m, r2 = t%m;

	int ml = min(l1, l2);
	int mr = max(r1,r2);

	if(l1 <= l2 && r1 >= r2){
		for(int i = 0; i<c.size(); i++){
			int cd = c[i]/m, cf = c[i]%m;
			if( cd>=ml && cd<=(l1+l2-ml) && cf <= mr && cf >= (r1 + r2-mr) ){
				return c[i];
			}
		}
	}
	return c[0];
}

// int main()
// {
// 	ios_base::sync_with_stdio(false); cin.tie(NULL);

// 	return 0;
// }

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 768 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 323 ms 912 KB Output is correct
2 Correct 268 ms 908 KB Output is correct
3 Correct 484 ms 684 KB Output is correct
4 Correct 382 ms 936 KB Output is correct
5 Correct 349 ms 936 KB Output is correct
6 Correct 251 ms 908 KB Output is correct
7 Correct 275 ms 684 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 0 ms 1016 KB Output is correct
11 Correct 347 ms 684 KB Output is correct
12 Correct 319 ms 1164 KB Output is correct
13 Correct 312 ms 1652 KB Output is correct
14 Correct 271 ms 684 KB Output is correct
15 Correct 26 ms 900 KB Output is correct
16 Correct 41 ms 844 KB Output is correct
17 Correct 57 ms 1424 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 684 KB Output is correct
2 Correct 390 ms 684 KB Output is correct
3 Correct 361 ms 684 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 0 ms 772 KB Output is correct
7 Correct 329 ms 684 KB Output is correct
8 Correct 520 ms 684 KB Output is correct
9 Correct 380 ms 684 KB Output is correct
10 Correct 359 ms 684 KB Output is correct
11 Correct 2 ms 764 KB Output is correct
12 Correct 2 ms 764 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 1 ms 1160 KB Output is correct
15 Correct 0 ms 768 KB Output is correct
16 Correct 307 ms 684 KB Output is correct
17 Correct 276 ms 684 KB Output is correct
18 Correct 280 ms 684 KB Output is correct
19 Correct 282 ms 684 KB Output is correct
20 Correct 293 ms 684 KB Output is correct

Subtask #5
26.3205 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 328 ms 1096 KB Partially correct
2 Partially correct 258 ms 900 KB Partially correct
3 Partially correct 518 ms 684 KB Partially correct
4 Partially correct 397 ms 684 KB Partially correct
5 Partially correct 378 ms 684 KB Partially correct
6 Partially correct 276 ms 1160 KB Partially correct
7 Partially correct 270 ms 684 KB Partially correct
8 Partially correct 1 ms 768 KB Partially correct
9 Partially correct 2 ms 764 KB Partially correct
10 Partially correct 0 ms 764 KB Partially correct
11 Partially correct 273 ms 1128 KB Partially correct
12 Partially correct 313 ms 848 KB Partially correct
13 Partially correct 524 ms 940 KB Partially correct
14 Partially correct 361 ms 684 KB Partially correct
15 Partially correct 350 ms 684 KB Partially correct
16 Partially correct 287 ms 684 KB Partially correct
17 Partially correct 359 ms 684 KB Partially correct
18 Partially correct 263 ms 1144 KB Partially correct
19 Partially correct 278 ms 1264 KB Partially correct
20 Partially correct 271 ms 684 KB Partially correct
21 Partially correct 31 ms 904 KB Partially correct
22 Partially correct 38 ms 844 KB Partially correct
23 Partially correct 58 ms 1132 KB Partially correct
24 Partially correct 2 ms 768 KB Partially correct
25 Partially correct 3 ms 768 KB Partially correct
26 Partially correct 3 ms 764 KB Partially correct
27 Partially correct 1 ms 768 KB Partially correct
28 Partially correct 0 ms 768 KB Partially correct
29 Partially correct 266 ms 684 KB Partially correct
30 Partially correct 286 ms 684 KB Partially correct
31 Partially correct 292 ms 684 KB Partially correct
32 Partially correct 307 ms 684 KB Partially correct
33 Partially correct 303 ms 684 KB Partially correct
34 Partially correct 186 ms 904 KB Partially correct
35 Partially correct 248 ms 1284 KB Partially correct
36 Partially correct 259 ms 1160 KB Partially correct
37 Partially correct 259 ms 1148 KB Partially correct
38 Partially correct 266 ms 1260 KB Partially correct
39 Partially correct 260 ms 1580 KB Partially correct
40 Partially correct 273 ms 1272 KB Partially correct
41 Partially correct 261 ms 1148 KB Partially correct
42 Partially correct 39 ms 868 KB Partially correct
43 Partially correct 62 ms 928 KB Partially correct
44 Partially correct 79 ms 920 KB Partially correct
45 Partially correct 86 ms 896 KB Partially correct
46 Partially correct 173 ms 864 KB Partially correct
47 Partially correct 169 ms 880 KB Partially correct
48 Partially correct 39 ms 1128 KB Partially correct
49 Partially correct 35 ms 1140 KB Partially correct