oj.uz

Submission #1077165

# Submission time Handle Problem Language Result Execution time Memory
1077165 2024-08-27T02:14:09 Z mindiyak Stations (IOI20_stations) C++14
16 / 100
 630 ms 968 KB 
#include "stations.h"
#include <vector>
#include <queue>
#include <iostream>

#include <algorithm>
using namespace std;

vector<vector<int>> paths(1001);
vector<int> dist(1001,-1);

void dfs(int pos,int len){
	if(dist[pos] != -1)return;
	dist[pos] = len;
	for(int i:paths[pos])dfs(i,len+1);
}


std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
	paths = vector<vector<int>>(1001);
	dist = vector<int>(1001,-1);

	for(int i = 0;i<n-1;i++){
		paths[u[i]].push_back(v[i]);
		paths[v[i]].push_back(u[i]);
	}

	int head = 0;
	for (int i = 0; i < n; i++) {
		if(paths[i].size() > 2){
			head = i;
		}
	}

	dist[head] = 0;
	int cnt = 1;
	for(int i:paths[head]){
		dfs(i,cnt*1000);
		cnt ++;
	}

	// cerr << head << endl;
	for (int i = 0; i < n; i++) {
		labels[i] = dist[i];
		// cerr << labels[i] << " ";
	}
	// cerr << endl;
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	sort(c.begin(),c.end());
	if (c.size() == 1) return c[0];

	if(s == 0){
		for (int v : c)
			if (v/1000 == t/1000)
				return v;
	}

	for (int v : c)
        if (v == t)
            return t;
		
	if((t/1000) != (s/1000))return c[0];
	if(t>=s)return c[1];
	return c[0];
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 684 KB Output is correct
2 Correct 308 ms 684 KB Output is correct
3 Correct 623 ms 684 KB Output is correct
4 Correct 485 ms 684 KB Output is correct
5 Correct 385 ms 684 KB Output is correct
6 Correct 304 ms 684 KB Output is correct
7 Correct 289 ms 708 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 3 ms 776 KB Output is correct
10 Correct 1 ms 776 KB Output is correct
11 Correct 427 ms 684 KB Output is correct
12 Correct 372 ms 932 KB Output is correct
13 Correct 312 ms 968 KB Output is correct
14 Correct 322 ms 684 KB Output is correct
15 Correct 33 ms 768 KB Output is correct
16 Correct 45 ms 684 KB Output is correct
17 Correct 64 ms 728 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 684 KB Output is correct
2 Correct 440 ms 684 KB Output is correct
3 Correct 403 ms 684 KB Output is correct
4 Correct 2 ms 776 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 0 ms 776 KB Output is correct
7 Correct 403 ms 684 KB Output is correct
8 Correct 628 ms 948 KB Output is correct
9 Correct 472 ms 684 KB Output is correct
10 Correct 402 ms 688 KB Output is correct
11 Incorrect 1 ms 344 KB Invalid labels (duplicates values). scenario=5, label=1001
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 367 ms 684 KB Partially correct
2 Partially correct 351 ms 684 KB Partially correct
3 Correct 630 ms 684 KB Output is correct
4 Partially correct 468 ms 684 KB Partially correct
5 Partially correct 401 ms 684 KB Partially correct
6 Partially correct 310 ms 684 KB Partially correct
7 Partially correct 302 ms 684 KB Partially correct
8 Partially correct 2 ms 776 KB Partially correct
9 Partially correct 2 ms 776 KB Partially correct
10 Partially correct 0 ms 768 KB Partially correct
11 Incorrect 4 ms 460 KB Invalid labels (duplicates values). scenario=0, label=1009
12 Halted 0 ms 0 KB -