oj.uz

Submission #429888

# Submission time Handle Problem Language Result Execution time Memory
429888 2021-06-16T10:16:32 Z dreezy Stations (IOI20_stations) C++17
16 / 100
 1244 ms 792 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back

vector<int> labels;
vector<vector<int>> graph;

void dfs(int n,int p,  int curlabel){
	labels[n] = curlabel;
	for(int adj : graph[n])
	{
		if(adj != p)
			dfs(adj, n, curlabel + 1);
	}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> cnt(n);
	labels.assign(n, 0);
	graph.assign( n, vector<int>());
	for (int i = 0; i < n - 1; i++) {
		//cout << u[i]<<", "<<v[i]<<endl;
		cnt[u[i]]++;
		cnt[v[i]]++;
		graph[u[i]].pb(v[i]);
		graph[v[i]].pb(u[i]);
	}
	
	int root = 0;
	for(int i=0; i<n; i++)
		if(cnt[i] >2){
			root = i;
			break;
		}
		
	labels[root] = 0;
	int counter = 0;
	for(int branch : graph[root]){
		dfs(branch, root,counter * 1000 +1);
		counter++;
	}
	
	
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	int startbranch = s/1000;
	int endbranch = t/1000;
	if(s == 0){
		return endbranch * 1000 + 1;
	}
	
	if(startbranch == endbranch){
		if(s < t)
			return s + 1;
		
			
	}
	
	if( (s - 1) % 1000 == 0)
			return 0;
		return s -1;
}


/************/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 404 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 720 ms 596 KB Output is correct
2 Correct 559 ms 604 KB Output is correct
3 Correct 970 ms 464 KB Output is correct
4 Correct 915 ms 488 KB Output is correct
5 Correct 859 ms 468 KB Output is correct
6 Correct 684 ms 616 KB Output is correct
7 Correct 548 ms 584 KB Output is correct
8 Correct 4 ms 508 KB Output is correct
9 Correct 3 ms 452 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 948 ms 488 KB Output is correct
12 Correct 588 ms 680 KB Output is correct
13 Correct 844 ms 792 KB Output is correct
14 Correct 580 ms 548 KB Output is correct
15 Correct 71 ms 532 KB Output is correct
16 Correct 101 ms 528 KB Output is correct
17 Correct 184 ms 488 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1244 ms 456 KB Output is correct
2 Correct 958 ms 468 KB Output is correct
3 Correct 775 ms 464 KB Output is correct
4 Correct 3 ms 448 KB Output is correct
5 Correct 4 ms 400 KB Output is correct
6 Correct 2 ms 448 KB Output is correct
7 Correct 768 ms 484 KB Output is correct
8 Correct 1107 ms 520 KB Output is correct
9 Correct 1099 ms 400 KB Output is correct
10 Correct 715 ms 400 KB Output is correct
11 Incorrect 1 ms 256 KB Invalid labels (duplicates values). scenario=5, label=2
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 697 ms 712 KB Partially correct
2 Partially correct 546 ms 664 KB Partially correct
3 Correct 1041 ms 400 KB Output is correct
4 Partially correct 990 ms 400 KB Partially correct
5 Partially correct 690 ms 488 KB Partially correct
6 Partially correct 517 ms 728 KB Partially correct
7 Partially correct 539 ms 528 KB Partially correct
8 Partially correct 4 ms 468 KB Partially correct
9 Correct 7 ms 468 KB Output is correct
10 Partially correct 2 ms 468 KB Partially correct
11 Incorrect 7 ms 384 KB Invalid labels (duplicates values). scenario=0, label=3
12 Halted 0 ms 0 KB -