oj.uz

Submission #320506

# Submission time Handle Problem Language Result Execution time Memory
320506 2020-11-08T22:13:58 Z Ambok Stations (IOI20_stations) C++14
100 / 100
 1002 ms 1376 KB 
#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
int coun=0; 
vector < vector <int> > vec(2000);
vector <int> L(2000);
void dfs (int x, int y, int h)
	{
		if (h%2==0) L[x]=coun;
		coun++;
		for (int i=0; i<vec[x].size(); i++)
		{
			if (vec[x][i]==y) continue;
			dfs(vec[x][i], x, h+1);
		}
		if (h%2==1) L[x]=coun;
		h--; coun++;
	}
vector <int> label(int n, int k, vector <int> u, vector <int> v)
{
	int s, h, i;
	L.resize(n);
	vec.resize(n);
	
	for (i=0; i<n; i++)
	{
		vec[i].clear();
	}
	
	for (i=0; i<n-1; i++)
	{
		vec[u[i]].push_back(v[i]);
		vec[v[i]].push_back(u[i]);
	}
	
	L[0]=0; coun=0;
	dfs (0, -1, 0);
	
	vector < vector < int > > d;
	for(int i = 0; i < n; ++i) 
	{
	    d.push_back({L[i], i});
	}
	sort(d.begin(), d.end());
	
	for(int i=0; i<n; i++) 
	{
	    L[d[i][1]] = i;
	}
	
	return L;
}
int find_next_station(int s, int t, vector <int>c)
{
	int n=c.size(), i;
	int in[n+1], out[n+1];
	
	for (i=0; i<n; i++)
	in[i]=0, out[i]=0;
	
	if (n==1) return c[0];
	
	if (s==0)
	{
		in[n]=s;
		out[n]=c[n-1]+1;
		
		for (i=0; i<n; i++)
		out[i]=c[i];
		
		in[0]=s+1;
		for (i=1; i<n; i++)
		{
			in[i]=out[i-1]+1;
		}
		
		for (i=0; i<n; i++)
			{
				if (t>=in[i] && t<=out[i]) return c[i];
			}
	}
	
	if (s>c[n-1])
	{
		in[n]=c[1]-1;
		out[n]=s;
		
		for (i=0; i<n; i++)
		in[i]=c[i];
		
		for (i=1; i<n; i++)
		{
			if (i==n-1) out[n-1]=s-1;
			else out[i]=in[i+1]-1;
		}
	
		for (i=1; i<n; i++)
			{
				if (t>=in[i] && t<=out[i]) return c[i];
			}
		
		return c[0];
	}
	else 
	{
		in[n]=s;
		out[n]=c[n-2]+1;
		
		for (i=0; i<n; i++)
		out[i]=c[i];
		
		in[0]=s+1;
		
		for (i=1; i<n; i++)
		{
			in[i]=out[i-1]+1;
		}
		
		for (i=0; i<n-1; i++)
			{
				if (t>=in[i] && t<=out[i]) return c[i];
			}
	
		return c[n-1];	
	}
}

Compilation message

stations.cpp: In function 'void dfs(int, int, int)':
stations.cpp:11:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |   for (int i=0; i<vec[x].size(); i++)
      |                 ~^~~~~~~~~~~~~~
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:21:6: warning: unused variable 's' [-Wunused-variable]
   21 |  int s, h, i;
      |      ^
stations.cpp:21:9: warning: unused variable 'h' [-Wunused-variable]
   21 |  int s, h, i;
      |         ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 1224 KB Output is correct
2 Correct 535 ms 1240 KB Output is correct
3 Correct 1002 ms 884 KB Output is correct
4 Correct 835 ms 920 KB Output is correct
5 Correct 629 ms 864 KB Output is correct
6 Correct 463 ms 1236 KB Output is correct
7 Correct 507 ms 992 KB Output is correct
8 Correct 3 ms 960 KB Output is correct
9 Correct 4 ms 924 KB Output is correct
10 Correct 2 ms 960 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 992 KB Output is correct
2 Correct 585 ms 1068 KB Output is correct
3 Correct 988 ms 916 KB Output is correct
4 Correct 698 ms 864 KB Output is correct
5 Correct 703 ms 1024 KB Output is correct
6 Correct 475 ms 992 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 1364 KB Output is correct
2 Correct 494 ms 1228 KB Output is correct
3 Correct 862 ms 944 KB Output is correct
4 Correct 760 ms 912 KB Output is correct
5 Correct 583 ms 736 KB Output is correct
6 Correct 480 ms 1120 KB Output is correct
7 Correct 494 ms 992 KB Output is correct
8 Correct 4 ms 968 KB Output is correct
9 Correct 4 ms 732 KB Output is correct
10 Correct 1 ms 968 KB Output is correct
11 Correct 634 ms 916 KB Output is correct
12 Correct 554 ms 1240 KB Output is correct
13 Correct 585 ms 1120 KB Output is correct
14 Correct 482 ms 1072 KB Output is correct
15 Correct 56 ms 916 KB Output is correct
16 Correct 90 ms 1080 KB Output is correct
17 Correct 104 ms 1040 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 971 ms 916 KB Output is correct
2 Correct 733 ms 1024 KB Output is correct
3 Correct 604 ms 736 KB Output is correct
4 Correct 2 ms 928 KB Output is correct
5 Correct 4 ms 736 KB Output is correct
6 Correct 2 ms 924 KB Output is correct
7 Correct 621 ms 1044 KB Output is correct
8 Correct 976 ms 876 KB Output is correct
9 Correct 730 ms 736 KB Output is correct
10 Correct 680 ms 916 KB Output is correct
11 Correct 5 ms 928 KB Output is correct
12 Correct 6 ms 1024 KB Output is correct
13 Correct 5 ms 864 KB Output is correct
14 Correct 3 ms 864 KB Output is correct
15 Correct 2 ms 864 KB Output is correct
16 Correct 478 ms 992 KB Output is correct
17 Correct 518 ms 920 KB Output is correct
18 Correct 465 ms 924 KB Output is correct
19 Correct 497 ms 920 KB Output is correct
20 Correct 495 ms 920 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 992 KB Output is correct
2 Correct 544 ms 1240 KB Output is correct
3 Correct 883 ms 912 KB Output is correct
4 Correct 706 ms 864 KB Output is correct
5 Correct 714 ms 928 KB Output is correct
6 Correct 492 ms 1376 KB Output is correct
7 Correct 554 ms 1028 KB Output is correct
8 Correct 2 ms 864 KB Output is correct
9 Correct 5 ms 736 KB Output is correct
10 Correct 2 ms 928 KB Output is correct
11 Correct 593 ms 1120 KB Output is correct
12 Correct 529 ms 992 KB Output is correct
13 Correct 894 ms 864 KB Output is correct
14 Correct 648 ms 916 KB Output is correct
15 Correct 633 ms 1120 KB Output is correct
16 Correct 444 ms 1064 KB Output is correct
17 Correct 589 ms 916 KB Output is correct
18 Correct 439 ms 1272 KB Output is correct
19 Correct 461 ms 1160 KB Output is correct
20 Correct 441 ms 1020 KB Output is correct
21 Correct 58 ms 904 KB Output is correct
22 Correct 74 ms 992 KB Output is correct
23 Correct 104 ms 1044 KB Output is correct
24 Correct 7 ms 736 KB Output is correct
25 Correct 5 ms 968 KB Output is correct
26 Correct 5 ms 736 KB Output is correct
27 Correct 4 ms 736 KB Output is correct
28 Correct 2 ms 924 KB Output is correct
29 Correct 529 ms 736 KB Output is correct
30 Correct 512 ms 1120 KB Output is correct
31 Correct 567 ms 736 KB Output is correct
32 Correct 504 ms 736 KB Output is correct
33 Correct 560 ms 1024 KB Output is correct
34 Correct 343 ms 864 KB Output is correct
35 Correct 418 ms 1328 KB Output is correct
36 Correct 473 ms 1180 KB Output is correct
37 Correct 460 ms 1148 KB Output is correct
38 Correct 440 ms 1292 KB Output is correct
39 Correct 458 ms 1136 KB Output is correct
40 Correct 521 ms 1156 KB Output is correct
41 Correct 583 ms 984 KB Output is correct
42 Correct 68 ms 1072 KB Output is correct
43 Correct 145 ms 1040 KB Output is correct
44 Correct 142 ms 1120 KB Output is correct
45 Correct 179 ms 1048 KB Output is correct
46 Correct 378 ms 1060 KB Output is correct
47 Correct 376 ms 1020 KB Output is correct
48 Correct 73 ms 1152 KB Output is correct
49 Correct 69 ms 1240 KB Output is correct