Submission #334925

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
334925	2020-12-10T09:44:12 Z	inwbear	Stations (IOI20_stations)	C++14	52.3244 / 100	1251 ms	1380 KB

stations

#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define imx INT_MAX
const long long MMX = (long long)(1e18);
typedef long long LL;
typedef pair<int,int> pii;
int nn,co[1005];
bitset<1005>go;
vector<int>v[1005];
void dfs(int N)
{
	go[N]=true;
	co[N]=nn*1000;
	for(int i=0;i<v[N].size();i++)
	{
		if(!go[v[N][i]])
		{
			dfs(v[N][i]);
		}
	}
	co[N]+=nn;
	nn++;
	return;
}
vector<int>label(int n,int k,vector<int>a,vector<int>b)
{
	vector<int>labels(n);
	nn=0;
	for(int i=0;i<1005;i++)v[i].clear(),go[i]=false;
	for(int i=0;i<a.size();i++)
	{
		v[a[i]].pb(b[i]);
		v[b[i]].pb(a[i]);
	}
	dfs(0);
	for(int i=0;i<n;i++)labels[i]=co[i];
	return labels;
}

int find_next_station(int s,int t,vector<int>c)
{
	int ss=s/1000,se=s%1000,ts=t/1000,te=t%1000,cs,ce,re;
	//printf("%d %d %d %d\n",ss,se,ts,te);
	if(ss<=ts&&se>=te)
	{
		for(int i=0;i<c.size();i++)
		{
			cs=c[i]/1000;
			ce=c[i]%1000;
			//printf("{%d %d}\n",cs,ce);
			if(ss<=cs&&se>=ce)
			{
				if(cs<=ts&&ce>=te)re=c[i];
			}
		}
	}
	else
	{
		for(int i=0;i<c.size();i++)
		{
			cs=c[i]/1000;
			ce=c[i]%1000;
			//printf("[%d %d]\n",cs,ce);
			if(cs<=ss&&ce>=se)re=c[i];
		}
	}
	return re;
}

Compilation message

stations.cpp: In function 'void dfs(int)':
stations.cpp:20:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0;i<v[N].size();i++)
      |              ~^~~~~~~~~~~~
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=0;i<a.size();i++)
      |              ~^~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i=0;i<c.size();i++)
      |               ~^~~~~~~~~
stations.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i=0;i<c.size();i++)
      |               ~^~~~~~~~~
stations.cpp:73:9: warning: 're' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |  return re;
      |         ^~

Subtask #1

0 / 5.0

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

Subtask #2

0 / 8.0

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

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	579 ms	1136 KB	Output is correct
2	Correct	497 ms	1080 KB	Output is correct
3	Correct	870 ms	1084 KB	Output is correct
4	Correct	729 ms	864 KB	Output is correct
5	Correct	584 ms	864 KB	Output is correct
6	Correct	531 ms	1092 KB	Output is correct
7	Correct	542 ms	1120 KB	Output is correct
8	Correct	3 ms	996 KB	Output is correct
9	Correct	4 ms	948 KB	Output is correct
10	Correct	2 ms	864 KB	Output is correct
11	Correct	615 ms	736 KB	Output is correct
12	Correct	526 ms	1120 KB	Output is correct
13	Correct	620 ms	1088 KB	Output is correct
14	Correct	625 ms	900 KB	Output is correct
15	Correct	72 ms	1024 KB	Output is correct
16	Correct	69 ms	864 KB	Output is correct
17	Correct	145 ms	864 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1251 ms	864 KB	Output is correct
2	Correct	661 ms	864 KB	Output is correct
3	Correct	647 ms	988 KB	Output is correct
4	Correct	3 ms	956 KB	Output is correct
5	Correct	4 ms	736 KB	Output is correct
6	Correct	2 ms	736 KB	Output is correct
7	Correct	582 ms	736 KB	Output is correct
8	Correct	871 ms	948 KB	Output is correct
9	Correct	646 ms	1084 KB	Output is correct
10	Correct	571 ms	948 KB	Output is correct
11	Correct	6 ms	956 KB	Output is correct
12	Correct	5 ms	864 KB	Output is correct
13	Correct	5 ms	864 KB	Output is correct
14	Correct	4 ms	864 KB	Output is correct
15	Correct	2 ms	736 KB	Output is correct
16	Correct	496 ms	736 KB	Output is correct
17	Correct	696 ms	864 KB	Output is correct
18	Correct	539 ms	948 KB	Output is correct
19	Correct	599 ms	1116 KB	Output is correct
20	Correct	516 ms	1076 KB	Output is correct

Subtask #5

26.3244 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	556 ms	1100 KB	Partially correct
2	Partially correct	477 ms	960 KB	Partially correct
3	Correct	934 ms	864 KB	Output is correct
4	Partially correct	770 ms	864 KB	Partially correct
5	Partially correct	701 ms	1076 KB	Partially correct
6	Partially correct	513 ms	1220 KB	Partially correct
7	Partially correct	484 ms	1024 KB	Partially correct
8	Partially correct	3 ms	736 KB	Partially correct
9	Correct	4 ms	776 KB	Output is correct
10	Partially correct	2 ms	736 KB	Partially correct
11	Partially correct	451 ms	736 KB	Partially correct
12	Partially correct	592 ms	908 KB	Partially correct
13	Correct	1018 ms	1076 KB	Output is correct
14	Partially correct	670 ms	1108 KB	Partially correct
15	Partially correct	629 ms	948 KB	Partially correct
16	Partially correct	562 ms	864 KB	Partially correct
17	Partially correct	654 ms	896 KB	Partially correct
18	Partially correct	476 ms	1008 KB	Partially correct
19	Partially correct	528 ms	1004 KB	Partially correct
20	Partially correct	521 ms	900 KB	Partially correct
21	Partially correct	54 ms	748 KB	Partially correct
22	Partially correct	86 ms	980 KB	Partially correct
23	Partially correct	121 ms	896 KB	Partially correct
24	Partially correct	6 ms	948 KB	Partially correct
25	Partially correct	7 ms	736 KB	Partially correct
26	Partially correct	6 ms	904 KB	Partially correct
27	Partially correct	5 ms	768 KB	Partially correct
28	Partially correct	2 ms	864 KB	Partially correct
29	Partially correct	684 ms	864 KB	Partially correct
30	Partially correct	501 ms	948 KB	Partially correct
31	Partially correct	664 ms	864 KB	Partially correct
32	Partially correct	638 ms	948 KB	Partially correct
33	Partially correct	599 ms	948 KB	Partially correct
34	Partially correct	372 ms	992 KB	Partially correct
35	Partially correct	475 ms	1208 KB	Partially correct
36	Partially correct	541 ms	1092 KB	Partially correct
37	Partially correct	545 ms	864 KB	Partially correct
38	Partially correct	543 ms	992 KB	Partially correct
39	Partially correct	461 ms	1264 KB	Partially correct
40	Partially correct	467 ms	1380 KB	Partially correct
41	Partially correct	459 ms	1116 KB	Partially correct
42	Partially correct	57 ms	1024 KB	Partially correct
43	Partially correct	113 ms	864 KB	Partially correct
44	Partially correct	133 ms	868 KB	Partially correct
45	Partially correct	150 ms	1120 KB	Partially correct
46	Partially correct	294 ms	864 KB	Partially correct
47	Partially correct	322 ms	996 KB	Partially correct
48	Partially correct	70 ms	1144 KB	Partially correct
49	Partially correct	68 ms	992 KB	Partially correct