oj.uz

Submission #1080213

# Submission time Handle Problem Language Result Execution time Memory
1080213 2024-08-29T08:01:48 Z UmairAhmadMirza Stations (IOI20_stations) C++17
52.3205 / 100
 676 ms 1176 KB 
#include <bits/stdc++.h>
using namespace std;

int const N=1005;
vector<int> adj[N];
int tim=-1;
int in[N],out[N];
int lab[N];
void dfs(int node,int par=-1){
	tim++;
	in[node]=tim;
	for(int i:adj[node])
		if(i!=par)
			dfs(i,node);
	out[node]=tim;
}
vector<int> solver(int n){
	for(int i=0;i<n;i++)
		if(adj[i].size()==1){
			dfs(i);
			break;
		}
	vector<int> val;
	for (int i = 0; i < n; ++i)
		val.push_back(in[i]);
	return val;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v){
	for (int i = 0; i < n; ++i)
	{
		adj[i].clear();
		tim=-1;
		in[i]=out[i]=0;
	}
	for (int i = 0; i < n-1; ++i)
	{
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	if(k<=1000)
		return solver(n);
	dfs(0);
	vector<int> val;
	for (int i = 0; i < n; ++i)
		val.push_back((in[i]*1000)+out[i]);
	// for(int i=0;i<n;i++)
	// 	cout<<val[i]<<' ';
	// cout<<endl;
	return val;
}
int fns(int s,int t,vector<int> c){
	if(c.size()==0)
		return c[0];
	if(c[0]>c[1])
		swap(c[0],c[1]);
	if(t<=c[0])
		return c[0];
	return c[1];
}
int find_next_station(int s, int t, vector<int> c){
	bool b=(s>1000 || t>1000);
	for(int i=0;i<c.size();i++)
		if(c[i]>1000)
			b=1;
	if(b==0)
		return fns(s,t,c);
	// cout<<s<<' '<<t<<endl;
	int n=c.size();
	int inn[n],outt[n];
	int ti=t/1000,to=t%1000;
	for (int i = 0; i < n; ++i)
	{
		inn[i]=c[i]/1000;
		outt[i]=c[i]%1000;
	}
	int si=s/1000,so=s%1000;
	for(int i=0;i<n;i++)
		if(inn[i]<=ti && to<=outt[i] && !(inn[i]<=si && so<=outt[i]))
			return c[i];
	
	for(int i=0;i<n;i++)
		if(inn[i]<=si && so<=outt[i])
			return c[i];
	return 0;
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 379 ms 684 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 302 ms 684 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 684 KB Output is correct
2 Correct 322 ms 684 KB Output is correct
3 Correct 616 ms 684 KB Output is correct
4 Correct 437 ms 684 KB Output is correct
5 Correct 416 ms 684 KB Output is correct
6 Correct 287 ms 684 KB Output is correct
7 Correct 292 ms 684 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 364 ms 684 KB Output is correct
12 Correct 266 ms 1028 KB Output is correct
13 Correct 275 ms 1012 KB Output is correct
14 Correct 303 ms 684 KB Output is correct
15 Correct 35 ms 772 KB Output is correct
16 Correct 45 ms 840 KB Output is correct
17 Correct 76 ms 684 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 684 KB Output is correct
2 Correct 386 ms 684 KB Output is correct
3 Correct 365 ms 804 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 1 ms 764 KB Output is correct
7 Correct 388 ms 684 KB Output is correct
8 Correct 676 ms 684 KB Output is correct
9 Correct 477 ms 684 KB Output is correct
10 Correct 444 ms 684 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 4 ms 760 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 0 ms 768 KB Output is correct
16 Correct 386 ms 684 KB Output is correct
17 Correct 406 ms 684 KB Output is correct
18 Correct 363 ms 684 KB Output is correct
19 Correct 360 ms 684 KB Output is correct
20 Correct 369 ms 688 KB Output is correct

Subtask #5
26.3205 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 371 ms 684 KB Partially correct
2 Partially correct 304 ms 684 KB Partially correct
3 Partially correct 633 ms 684 KB Partially correct
4 Partially correct 494 ms 684 KB Partially correct
5 Partially correct 416 ms 684 KB Partially correct
6 Partially correct 329 ms 1124 KB Partially correct
7 Partially correct 316 ms 684 KB Partially correct
8 Partially correct 2 ms 768 KB Partially correct
9 Partially correct 3 ms 768 KB Partially correct
10 Partially correct 1 ms 768 KB Partially correct
11 Partially correct 295 ms 684 KB Partially correct
12 Partially correct 344 ms 848 KB Partially correct
13 Partially correct 590 ms 808 KB Partially correct
14 Partially correct 454 ms 684 KB Partially correct
15 Partially correct 391 ms 684 KB Partially correct
16 Partially correct 316 ms 684 KB Partially correct
17 Partially correct 399 ms 804 KB Partially correct
18 Partially correct 363 ms 944 KB Partially correct
19 Partially correct 367 ms 784 KB Partially correct
20 Partially correct 320 ms 800 KB Partially correct
21 Partially correct 42 ms 768 KB Partially correct
22 Partially correct 43 ms 712 KB Partially correct
23 Partially correct 82 ms 684 KB Partially correct
24 Partially correct 3 ms 776 KB Partially correct
25 Partially correct 4 ms 764 KB Partially correct
26 Partially correct 4 ms 764 KB Partially correct
27 Partially correct 3 ms 776 KB Partially correct
28 Partially correct 1 ms 760 KB Partially correct
29 Partially correct 362 ms 684 KB Partially correct
30 Partially correct 387 ms 848 KB Partially correct
31 Partially correct 343 ms 684 KB Partially correct
32 Partially correct 318 ms 864 KB Partially correct
33 Partially correct 346 ms 684 KB Partially correct
34 Partially correct 244 ms 936 KB Partially correct
35 Partially correct 322 ms 928 KB Partially correct
36 Partially correct 327 ms 1048 KB Partially correct
37 Partially correct 334 ms 812 KB Partially correct
38 Partially correct 332 ms 808 KB Partially correct
39 Partially correct 322 ms 932 KB Partially correct
40 Partially correct 317 ms 940 KB Partially correct
41 Partially correct 361 ms 800 KB Partially correct
42 Partially correct 43 ms 760 KB Partially correct
43 Partially correct 78 ms 684 KB Partially correct
44 Partially correct 103 ms 688 KB Partially correct
45 Partially correct 97 ms 684 KB Partially correct
46 Partially correct 218 ms 936 KB Partially correct
47 Partially correct 229 ms 684 KB Partially correct
48 Partially correct 38 ms 760 KB Partially correct
49 Partially correct 34 ms 1176 KB Partially correct