oj.uz

Submission #334927

# Submission time Handle Problem Language Result Execution time Memory
334927 2020-12-10T09:48:14 Z inwbear Stations (IOI20_stations) C++14
57.3282 / 100
 1067 ms 1372 KB 
#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],st;
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]);
	}
	for(int i=0;i<n;i++)if(v[i].size()==1)st=i;
	dfs(st);
	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:53:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int i=0;i<c.size();i++)
      |               ~^~~~~~~~~
stations.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(int i=0;i<c.size();i++)
      |               ~^~~~~~~~~
stations.cpp:74:9: warning: 're' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |  return re;
      |         ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 1092 KB Output is correct
2 Correct 432 ms 1088 KB Output is correct
3 Correct 822 ms 736 KB Output is correct
4 Correct 659 ms 736 KB Output is correct
5 Correct 560 ms 1108 KB Output is correct
6 Correct 452 ms 1092 KB Output is correct
7 Correct 442 ms 864 KB Output is correct
8 Correct 3 ms 992 KB Output is correct
9 Correct 5 ms 864 KB Output is correct
10 Correct 2 ms 736 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 1004 KB Output is correct
2 Correct 470 ms 864 KB Output is correct
3 Correct 912 ms 948 KB Output is correct
4 Correct 603 ms 736 KB Output is correct
5 Correct 589 ms 1116 KB Output is correct
6 Correct 439 ms 992 KB Output is correct
7 Correct 464 ms 1108 KB Output is correct
8 Correct 3 ms 956 KB Output is correct
9 Correct 5 ms 864 KB Output is correct
10 Correct 2 ms 864 KB Output is correct
11 Correct 585 ms 992 KB Output is correct
12 Correct 435 ms 1220 KB Output is correct
13 Correct 453 ms 1184 KB Output is correct
14 Correct 446 ms 900 KB Output is correct
15 Correct 56 ms 948 KB Output is correct
16 Correct 66 ms 864 KB Output is correct
17 Correct 114 ms 892 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 861 ms 948 KB Output is correct
2 Correct 691 ms 864 KB Output is correct
3 Correct 538 ms 992 KB Output is correct
4 Correct 3 ms 948 KB Output is correct
5 Correct 4 ms 736 KB Output is correct
6 Correct 2 ms 736 KB Output is correct
7 Correct 544 ms 864 KB Output is correct
8 Correct 843 ms 948 KB Output is correct
9 Correct 614 ms 948 KB Output is correct
10 Correct 558 ms 736 KB Output is correct
11 Correct 5 ms 948 KB Output is correct
12 Correct 5 ms 864 KB Output is correct
13 Correct 4 ms 992 KB Output is correct
14 Correct 4 ms 956 KB Output is correct
15 Correct 2 ms 956 KB Output is correct
16 Correct 523 ms 736 KB Output is correct
17 Correct 521 ms 992 KB Output is correct
18 Correct 620 ms 736 KB Output is correct
19 Correct 646 ms 1096 KB Output is correct
20 Correct 504 ms 864 KB Output is correct

Subtask #5
26.3282 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 1248 KB Output is correct
2 Correct 478 ms 1088 KB Output is correct
3 Correct 1067 ms 956 KB Output is correct
4 Correct 751 ms 864 KB Output is correct
5 Correct 613 ms 948 KB Output is correct
6 Correct 509 ms 1092 KB Output is correct
7 Correct 432 ms 1116 KB Output is correct
8 Correct 3 ms 864 KB Output is correct
9 Correct 4 ms 736 KB Output is correct
10 Correct 2 ms 864 KB Output is correct
11 Partially correct 447 ms 864 KB Partially correct
12 Partially correct 608 ms 892 KB Partially correct
13 Correct 987 ms 864 KB Output is correct
14 Correct 838 ms 736 KB Output is correct
15 Correct 614 ms 864 KB Output is correct
16 Partially correct 474 ms 900 KB Partially correct
17 Partially correct 669 ms 948 KB Partially correct
18 Partially correct 434 ms 1120 KB Partially correct
19 Partially correct 552 ms 992 KB Partially correct
20 Partially correct 591 ms 992 KB Partially correct
21 Partially correct 59 ms 948 KB Partially correct
22 Partially correct 75 ms 928 KB Partially correct
23 Partially correct 135 ms 892 KB Partially correct
24 Partially correct 7 ms 736 KB Partially correct
25 Partially correct 7 ms 776 KB Partially correct
26 Partially correct 6 ms 956 KB Partially correct
27 Partially correct 5 ms 864 KB Partially correct
28 Partially correct 2 ms 956 KB Partially correct
29 Partially correct 573 ms 948 KB Partially correct
30 Partially correct 578 ms 960 KB Partially correct
31 Partially correct 497 ms 864 KB Partially correct
32 Partially correct 526 ms 736 KB Partially correct
33 Partially correct 627 ms 1108 KB Partially correct
34 Partially correct 380 ms 1088 KB Partially correct
35 Partially correct 489 ms 864 KB Partially correct
36 Partially correct 549 ms 992 KB Partially correct
37 Partially correct 612 ms 992 KB Partially correct
38 Partially correct 566 ms 1372 KB Partially correct
39 Partially correct 503 ms 992 KB Partially correct
40 Partially correct 569 ms 1120 KB Partially correct
41 Partially correct 543 ms 988 KB Partially correct
42 Partially correct 63 ms 896 KB Partially correct
43 Partially correct 119 ms 864 KB Partially correct
44 Partially correct 152 ms 1248 KB Partially correct
45 Partially correct 177 ms 988 KB Partially correct
46 Partially correct 300 ms 896 KB Partially correct
47 Partially correct 351 ms 864 KB Partially correct
48 Partially correct 59 ms 900 KB Partially correct
49 Partially correct 59 ms 864 KB Partially correct