oj.uz

Submission #305701

# Submission time Handle Problem Language Result Execution time Memory
305701 2020-09-23T20:20:59 Z arthurconmy Stations (IOI20_stations) C++14
16 / 100
 1077 ms 1140 KB 
#ifndef ARTHUR_LOCAL
	#include "stations.h"
#endif

#ifdef ARTHUR_LOCAL
	#include <bits/stdc++.h>
#endif

using namespace std;
using ll = long long;

vector<int> adj[1001];
bool vis[1001];
int curv;
int labellist[1001];

void dfs(int v)
{
	vis[v]=1;
	labellist[v]=++curv;

	for(auto u:adj[v])
	{
		if(!vis[u]) dfs(u);
		if(labellist[v]==0)
		{
			curv = int(curv/1000);
			curv++;
			curv *= 1000;
		}
	}
}

vector<int> label(int n, int k, vector<int> U, vector<int> V) 
{
	for(int i=0; i<n; i++)
	{
		adj[i].clear();
		vis[i]=0;

	}

	for(int i=0; i < n-1; i++)
	{
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}

	vector<int> labels(n);

	for(int i=0; i<n; i++)
	{
		if(i==n-1 || adj[i].size()>=3)
		{
			curv=-1;
			// cout << "dfs " << i << endl;
			dfs(i);
			break;
		}
	}

	for(int i=0; i<n; i++) labels[i]=labellist[i];

	return labels;
}

int find_next_station(int s, int t, vector<int> C) 
{
	if(C.size()==1) return C[0];

	if(s==0)
	{
		int cur = int(t/1000);
		cur*=1000;
		return cur+1;
	}

	if(t==0)
	{
		return C[0];
	}

	if(int(s/1000) == int(t/1000))
	{
		if(s<t) return C[1];
		else return C[0];
	}

	return C[0];
}

#ifdef ARTHUR_LOCAL
int main()
{
	vector<int> LL = label(6, 1000, {3, 2, 1, 1, 5}, {2, 1, 4, 5, 0});
	for(auto l:LL) cout << l << " ";
	cout << endl;
	return 0;
	cout << "ANS: " << find_next_station(0, 6, {1, 2}) << endl; 
}
#endif

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 768 KB Output is correct
2 Correct 483 ms 768 KB Output is correct
3 Correct 853 ms 776 KB Output is correct
4 Correct 768 ms 768 KB Output is correct
5 Correct 603 ms 768 KB Output is correct
6 Correct 546 ms 788 KB Output is correct
7 Correct 511 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 5 ms 892 KB Output is correct
10 Correct 1 ms 884 KB Output is correct
11 Correct 596 ms 768 KB Output is correct
12 Correct 485 ms 920 KB Output is correct
13 Correct 477 ms 888 KB Output is correct
14 Correct 511 ms 844 KB Output is correct
15 Correct 54 ms 768 KB Output is correct
16 Correct 64 ms 860 KB Output is correct
17 Correct 113 ms 828 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1077 ms 768 KB Output is correct
2 Correct 812 ms 884 KB Output is correct
3 Correct 592 ms 884 KB Output is correct
4 Correct 1 ms 888 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 1 ms 880 KB Output is correct
7 Correct 619 ms 1140 KB Output is correct
8 Correct 880 ms 884 KB Output is correct
9 Correct 749 ms 1024 KB Output is correct
10 Correct 649 ms 1024 KB Output is correct
11 Incorrect 6 ms 888 KB Wrong query response.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 606 ms 800 KB Partially correct
2 Partially correct 496 ms 924 KB Partially correct
3 Correct 1011 ms 884 KB Output is correct
4 Partially correct 760 ms 768 KB Partially correct
5 Partially correct 662 ms 884 KB Partially correct
6 Partially correct 564 ms 784 KB Partially correct
7 Partially correct 501 ms 768 KB Partially correct
8 Partially correct 2 ms 892 KB Partially correct
9 Partially correct 4 ms 888 KB Partially correct
10 Partially correct 1 ms 768 KB Partially correct
11 Incorrect 498 ms 784 KB Wrong query response.
12 Halted 0 ms 0 KB -