oj.uz

Submission #305700

# Submission time Handle Problem Language Result Execution time Memory
305700 2020-09-23T20:18:19 Z arthurconmy Stations (IOI20_stations) C++14
0 / 100
 887 ms 768 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;
	}

	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(2, 1000, {0}, {1});
	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 376 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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 545 ms 760 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 887 ms 768 KB Output is correct
2 Incorrect 742 ms 768 KB Wrong query response.
3 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 564 ms 768 KB Wrong query response.
2 Halted 0 ms 0 KB -