답안 #305154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
305154	2020-09-22T16:06:34 Z	ScarletS	기지국 (IOI20_stations)	C++17	52.3205 / 100	1299 ms	1032 KB

stations

#include "stations.h"
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

const int maxn = 1005;
int tin[maxn], tout[maxn], tr=-1;
vector<int> edges[maxn];

void dfs(int c, int p)
{
	tin[c]=++tr;
	for (int i : edges[c])
		if (i!=p)
			dfs(i,c);
	tout[c]=tr;
}

std::vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);
	tr=-1;
	for (int i=0;i<n;++i)
		edges[i].clear();
	for (int i=0;i<n-1;++i)
	{
		edges[u[i]].push_back(v[i]);
		edges[v[i]].push_back(u[i]);
	}
	dfs(0,-1);
	for (int i = 0; i < n; i++) {
		labels[i] = tin[i]*1000+tout[i];
	}
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c)
{
	/**cout<<s<<" "<<t<<"!\n";
	for (int i : c)
		cout<<i<<" ";
	cout<<"\n";**/
	if ((s/1000)<=(t/1000)&&(t%1000)<=(s%1000))
	{
		for (int i : c)
		{
			if ((i/1000)<=(t/1000)&&(t%1000)<=(i%1000)&&(s/1000)<=(i/1000)&&(i%1000)<=(s%1000))
				return i;
		}
	}
	else
	{
		for (int i : c)
		{
			if ((i/1000)<=(s/1000)&&(s%1000)<=(i%1000))
				return i;
		}
	}
	return 3141;
}
/**
int main()
{
	int n,k,x,y,q;
	cin>>n>>k;
	vector<int> a,b,v;
	for (int i=1;i<n;++i)
	{
		cin>>x>>y;
		a.push_back(x);
		b.push_back(y);
	}
	vector<int> ans = label(n,k,a,b);
	for (int i : ans)
	{
		cout<<i<<" "<<i/1000<<" "<<i%1000<<"\n";
	}
	cout<<"\n";
	cin>>q;
	while (q--)
	{
		cin>>x>>y;
		v.clear();
		for (int i=0;i<n-1;++i)
		{
			if (x==a[i])
				v.push_back(ans[b[i]]);
			if (x==b[i])
				v.push_back(ans[a[i]]);
		}
		//x = find_next_station(ans[x], ans[y], v);
		cout<<find_next_station(ans[x], ans[y], v)<<"\n";
	}
}**/

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	3 ms	384 KB	Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=6009
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	8 ms	456 KB	Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1511
2	Halted	0 ms	0 KB	-

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	670 ms	1008 KB	Output is correct
2	Correct	701 ms	1008 KB	Output is correct
3	Correct	1196 ms	800 KB	Output is correct
4	Correct	868 ms	768 KB	Output is correct
5	Correct	603 ms	768 KB	Output is correct
6	Correct	433 ms	768 KB	Output is correct
7	Correct	504 ms	768 KB	Output is correct
8	Correct	3 ms	768 KB	Output is correct
9	Correct	7 ms	776 KB	Output is correct
10	Correct	2 ms	768 KB	Output is correct
11	Correct	642 ms	820 KB	Output is correct
12	Correct	656 ms	948 KB	Output is correct
13	Correct	595 ms	832 KB	Output is correct
14	Correct	513 ms	768 KB	Output is correct
15	Correct	81 ms	768 KB	Output is correct
16	Correct	81 ms	896 KB	Output is correct
17	Correct	120 ms	768 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1160 ms	840 KB	Output is correct
2	Correct	625 ms	776 KB	Output is correct
3	Correct	609 ms	768 KB	Output is correct
4	Correct	3 ms	768 KB	Output is correct
5	Correct	5 ms	768 KB	Output is correct
6	Correct	2 ms	768 KB	Output is correct
7	Correct	866 ms	896 KB	Output is correct
8	Correct	1055 ms	864 KB	Output is correct
9	Correct	873 ms	928 KB	Output is correct
10	Correct	703 ms	768 KB	Output is correct
11	Correct	7 ms	776 KB	Output is correct
12	Correct	7 ms	896 KB	Output is correct
13	Correct	5 ms	768 KB	Output is correct
14	Correct	5 ms	928 KB	Output is correct
15	Correct	2 ms	768 KB	Output is correct
16	Correct	692 ms	1024 KB	Output is correct
17	Correct	513 ms	768 KB	Output is correct
18	Correct	512 ms	768 KB	Output is correct
19	Correct	517 ms	896 KB	Output is correct
20	Correct	507 ms	768 KB	Output is correct

Subtask #5
26.3205 / 61.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	773 ms	1016 KB	Partially correct
2	Partially correct	763 ms	896 KB	Partially correct
3	Partially correct	1299 ms	768 KB	Partially correct
4	Partially correct	750 ms	908 KB	Partially correct
5	Partially correct	695 ms	904 KB	Partially correct
6	Partially correct	529 ms	768 KB	Partially correct
7	Partially correct	532 ms	768 KB	Partially correct
8	Partially correct	4 ms	776 KB	Partially correct
9	Partially correct	4 ms	896 KB	Partially correct
10	Partially correct	2 ms	904 KB	Partially correct
11	Partially correct	519 ms	768 KB	Partially correct
12	Partially correct	708 ms	896 KB	Partially correct
13	Partially correct	1045 ms	808 KB	Partially correct
14	Partially correct	814 ms	896 KB	Partially correct
15	Partially correct	649 ms	768 KB	Partially correct
16	Partially correct	542 ms	896 KB	Partially correct
17	Partially correct	848 ms	896 KB	Partially correct
18	Partially correct	614 ms	896 KB	Partially correct
19	Partially correct	602 ms	896 KB	Partially correct
20	Partially correct	572 ms	768 KB	Partially correct
21	Partially correct	82 ms	840 KB	Partially correct
22	Partially correct	90 ms	856 KB	Partially correct
23	Partially correct	120 ms	896 KB	Partially correct
24	Partially correct	6 ms	896 KB	Partially correct
25	Partially correct	5 ms	976 KB	Partially correct
26	Partially correct	5 ms	800 KB	Partially correct
27	Partially correct	4 ms	768 KB	Partially correct
28	Partially correct	2 ms	768 KB	Partially correct
29	Partially correct	699 ms	768 KB	Partially correct
30	Partially correct	637 ms	1024 KB	Partially correct
31	Partially correct	554 ms	784 KB	Partially correct
32	Partially correct	566 ms	896 KB	Partially correct
33	Partially correct	577 ms	768 KB	Partially correct
34	Partially correct	382 ms	768 KB	Partially correct
35	Partially correct	545 ms	1024 KB	Partially correct
36	Partially correct	660 ms	928 KB	Partially correct
37	Partially correct	551 ms	892 KB	Partially correct
38	Partially correct	584 ms	768 KB	Partially correct
39	Partially correct	548 ms	968 KB	Partially correct
40	Partially correct	524 ms	768 KB	Partially correct
41	Partially correct	557 ms	816 KB	Partially correct
42	Partially correct	81 ms	768 KB	Partially correct
43	Partially correct	114 ms	904 KB	Partially correct
44	Partially correct	150 ms	908 KB	Partially correct
45	Partially correct	179 ms	1024 KB	Partially correct
46	Partially correct	354 ms	768 KB	Partially correct
47	Partially correct	404 ms	768 KB	Partially correct
48	Partially correct	87 ms	1032 KB	Partially correct
49	Partially correct	90 ms	1024 KB	Partially correct

답안 #305154

Compilation message

Subtask #1 0 / 5.0

Subtask #2 0 / 8.0

Subtask #3 16.0 / 16.0

Subtask #4 10.0 / 10.0

Subtask #5 26.3205 / 61.0

Subtask #1
0 / 5.0

Subtask #2
0 / 8.0

Subtask #3
16.0 / 16.0

Subtask #4
10.0 / 10.0

Subtask #5
26.3205 / 61.0