oj.uz

Submission #305154

# Submission time Handle Problem Language Result Execution time Memory
305154 2020-09-22T16:06:34 Z ScarletS Stations (IOI20_stations) C++17
52.3205 / 100
 1299 ms 1032 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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