oj.uz

Submission #719362

# Submission time Handle Problem Language Result Execution time Memory
719362 2023-04-05T20:40:25 Z mseebacher Stations (IOI20_stations) C++17
16 / 100
 875 ms 660 KB 
#include "stations.h"
#include <bits/stdc++.h> 

using namespace std;

#define MAXI (int)1e3+10

vector<int> ad[MAXI];
vector<int> labels;


// 1 .. 1e3
// 1e3+1 ... 2e3
void dfs(int x,int e){
	for(auto s: ad[x]){
		if(s == e) continue;
		labels[s] = labels[x]+1e3;
		dfs(s,x);
	}
}


vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	labels.assign(n,0);
	for(int i = 0;i<MAXI;i++) ad[i].clear();
	
	for(int i = 0;i<n-1;i++){
		ad[u[i]].push_back(v[i]);
		ad[v[i]].push_back(u[i]);
	}
	int start = 0;
	for(int i = 0;i<n;i++){
		if(ad[i].size() >= 3){
			start = i;
			break;
		}
	}
	int cnt = 1;
	labels[start] = 0;
	for(auto s: ad[start]){
		labels[s] = cnt++;
		dfs(s,start);
	}
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	if(s%1000 != t%1000){
		if(s == 0) return t%1000;
		return s > 999 ? s-1e3 : 0;
	}
	return s > t ? s-1e3 : s+1e3;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 644 KB Output is correct
2 Correct 448 ms 536 KB Output is correct
3 Correct 804 ms 416 KB Output is correct
4 Correct 623 ms 528 KB Output is correct
5 Correct 635 ms 532 KB Output is correct
6 Correct 527 ms 544 KB Output is correct
7 Correct 462 ms 552 KB Output is correct
8 Correct 3 ms 496 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 599 ms 416 KB Output is correct
12 Correct 503 ms 660 KB Output is correct
13 Correct 456 ms 636 KB Output is correct
14 Correct 542 ms 548 KB Output is correct
15 Correct 52 ms 472 KB Output is correct
16 Correct 52 ms 584 KB Output is correct
17 Correct 120 ms 544 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 834 ms 536 KB Output is correct
2 Correct 612 ms 416 KB Output is correct
3 Correct 611 ms 544 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 4 ms 500 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 561 ms 416 KB Output is correct
8 Correct 869 ms 420 KB Output is correct
9 Correct 682 ms 528 KB Output is correct
10 Correct 608 ms 420 KB Output is correct
11 Incorrect 1 ms 208 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 543 ms 528 KB Partially correct
2 Partially correct 461 ms 548 KB Partially correct
3 Correct 875 ms 416 KB Output is correct
4 Partially correct 633 ms 528 KB Partially correct
5 Partially correct 591 ms 528 KB Partially correct
6 Partially correct 429 ms 528 KB Partially correct
7 Partially correct 409 ms 544 KB Partially correct
8 Partially correct 1 ms 500 KB Partially correct
9 Partially correct 5 ms 492 KB Partially correct
10 Partially correct 2 ms 492 KB Partially correct
11 Incorrect 3 ms 316 KB Invalid labels (duplicates values). scenario=0, label=2001
12 Halted 0 ms 0 KB -