Submission #341690

# Submission time Handle Problem Language Result Execution time Memory
341690 2020-12-30T12:29:31 Z ogibogi2004 Stations (IOI20_stations) C++14
52.3205 / 100
941 ms 1248 KB
#include "stations.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define time afds
const int MAXN=1024;
vector<int>g[MAXN];
int in_time[MAXN],out_time[MAXN],time=-1;
void dfs(int u,int par)
{
	in_time[u]=++time;
	for(auto v:g[u])
	{
		if(v==par)continue;
		dfs(v,u);
	}
	out_time[u]=time;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);
	time=-1;
	for(int i=0;i<=n;i++)g[i].clear();
	for(int i=0;i<u.size();i++)
	{
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	dfs(0,-1);
	for (int i = 0; i < n; i++) {
		if(in_time[i]*1000+out_time[i]<=k)labels[i] = in_time[i]*1000+out_time[i];
		else labels[i]=in_time[i];
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	int in_s=s/1000,out_s=s%1000;
	int in_t=t/1000,out_t=t%1000;
	if(!(in_t>=in_s&&out_t<=out_s))
	{
		for(auto xd:c)
		{
			int in1=xd/1000,out1=xd%1000;
			if(in1<=in_s&&out1>=out_s)
			{
				return xd;
			}
		}
	}
	else
	{
		for(auto xd:c)
		{
			int in1=xd/1000,out1=xd%1000;
			if(in1<=in_t&&out1>=out_t&&in_s<=in1&&out_s>=out1)
			{
				return xd;
			}
		}
	}
	return 0;
}

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:23:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int i=0;i<u.size();i++)
      |              ~^~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 604 KB Invalid labels (duplicates values). scenario=0, label=9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 364 KB Invalid labels (duplicates values). scenario=0, label=995
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 530 ms 992 KB Output is correct
2 Correct 454 ms 1100 KB Output is correct
3 Correct 887 ms 944 KB Output is correct
4 Correct 680 ms 736 KB Output is correct
5 Correct 606 ms 944 KB Output is correct
6 Correct 463 ms 1104 KB Output is correct
7 Correct 441 ms 736 KB Output is correct
8 Correct 3 ms 984 KB Output is correct
9 Correct 5 ms 992 KB Output is correct
10 Correct 1 ms 944 KB Output is correct
11 Correct 604 ms 736 KB Output is correct
12 Correct 444 ms 1112 KB Output is correct
13 Correct 493 ms 992 KB Output is correct
14 Correct 501 ms 736 KB Output is correct
15 Correct 72 ms 936 KB Output is correct
16 Correct 89 ms 864 KB Output is correct
17 Correct 128 ms 736 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 929 ms 736 KB Output is correct
2 Correct 727 ms 944 KB Output is correct
3 Correct 675 ms 944 KB Output is correct
4 Correct 3 ms 864 KB Output is correct
5 Correct 4 ms 736 KB Output is correct
6 Correct 1 ms 736 KB Output is correct
7 Correct 665 ms 944 KB Output is correct
8 Correct 941 ms 864 KB Output is correct
9 Correct 660 ms 944 KB Output is correct
10 Correct 602 ms 964 KB Output is correct
11 Correct 6 ms 864 KB Output is correct
12 Correct 4 ms 736 KB Output is correct
13 Correct 6 ms 736 KB Output is correct
14 Correct 5 ms 736 KB Output is correct
15 Correct 2 ms 736 KB Output is correct
16 Correct 654 ms 736 KB Output is correct
17 Correct 657 ms 1072 KB Output is correct
18 Correct 671 ms 952 KB Output is correct
19 Correct 656 ms 1024 KB Output is correct
20 Correct 656 ms 1108 KB Output is correct
# Verdict Execution time Memory Grader output
1 Partially correct 642 ms 864 KB Partially correct
2 Partially correct 484 ms 1120 KB Partially correct
3 Partially correct 912 ms 736 KB Partially correct
4 Partially correct 740 ms 864 KB Partially correct
5 Partially correct 641 ms 1020 KB Partially correct
6 Partially correct 611 ms 992 KB Partially correct
7 Partially correct 603 ms 876 KB Partially correct
8 Partially correct 3 ms 736 KB Partially correct
9 Partially correct 5 ms 736 KB Partially correct
10 Partially correct 2 ms 736 KB Partially correct
11 Partially correct 506 ms 736 KB Partially correct
12 Partially correct 770 ms 1036 KB Partially correct
13 Partially correct 905 ms 864 KB Partially correct
14 Partially correct 685 ms 952 KB Partially correct
15 Partially correct 636 ms 944 KB Partially correct
16 Partially correct 502 ms 1024 KB Partially correct
17 Partially correct 700 ms 944 KB Partially correct
18 Partially correct 544 ms 1004 KB Partially correct
19 Partially correct 549 ms 1112 KB Partially correct
20 Partially correct 438 ms 896 KB Partially correct
21 Partially correct 58 ms 992 KB Partially correct
22 Partially correct 79 ms 864 KB Partially correct
23 Partially correct 102 ms 888 KB Partially correct
24 Partially correct 7 ms 944 KB Partially correct
25 Partially correct 6 ms 736 KB Partially correct
26 Partially correct 5 ms 864 KB Partially correct
27 Partially correct 4 ms 736 KB Partially correct
28 Partially correct 2 ms 952 KB Partially correct
29 Partially correct 484 ms 736 KB Partially correct
30 Partially correct 524 ms 944 KB Partially correct
31 Partially correct 601 ms 864 KB Partially correct
32 Partially correct 653 ms 1072 KB Partially correct
33 Partially correct 500 ms 944 KB Partially correct
34 Partially correct 361 ms 1236 KB Partially correct
35 Partially correct 432 ms 1220 KB Partially correct
36 Partially correct 625 ms 992 KB Partially correct
37 Partially correct 595 ms 1108 KB Partially correct
38 Partially correct 595 ms 1236 KB Partially correct
39 Partially correct 456 ms 1248 KB Partially correct
40 Partially correct 523 ms 1124 KB Partially correct
41 Partially correct 464 ms 1244 KB Partially correct
42 Partially correct 85 ms 736 KB Partially correct
43 Partially correct 112 ms 736 KB Partially correct
44 Partially correct 146 ms 1104 KB Partially correct
45 Partially correct 161 ms 1116 KB Partially correct
46 Partially correct 328 ms 896 KB Partially correct
47 Partially correct 332 ms 736 KB Partially correct
48 Partially correct 66 ms 1132 KB Partially correct
49 Partially correct 60 ms 992 KB Partially correct