oj.uz

Submission #377817

# Submission time Handle Problem Language Result Execution time Memory
377817 2021-03-15T07:56:16 Z autumn_eel Stations (IOI20_stations) C++14
21 / 100
 1001 ms 1112 KB 
#include "stations.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<int(n);i++)
using namespace std;
typedef long long ll;

static vector<vector<int>>E;
static vector<int>labels;

void dfs(int v,int p,int l){
	labels[v]=l;
	for(int u:E[v]){
		if(u==p)continue;
		dfs(u,v,l+1);
	}
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v){
	E=vector<vector<int>>(n);
	labels=vector<int>(n);
	vector<int>deg(n);
	rep(i,n-1){
		E[u[i]].push_back(v[i]);
		E[v[i]].push_back(u[i]);
		deg[u[i]]++;
		deg[v[i]]++;
	}
	int s=max_element(deg.begin(),deg.end())-deg.begin();
	if(deg[s]==2){
		s=min_element(deg.begin(),deg.end())-deg.begin();
	}
	int x=1;
	for(int u:E[s]){
		dfs(u,s,x);
		x+=1000;
	}
	return labels;
}

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 976 KB Output is correct
2 Correct 505 ms 864 KB Output is correct
3 Correct 951 ms 896 KB Output is correct
4 Correct 751 ms 996 KB Output is correct
5 Correct 551 ms 736 KB Output is correct
6 Correct 426 ms 1084 KB Output is correct
7 Correct 507 ms 884 KB Output is correct
8 Correct 3 ms 756 KB Output is correct
9 Correct 4 ms 756 KB Output is correct
10 Correct 2 ms 868 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 492 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 629 ms 884 KB Output is correct
2 Correct 546 ms 864 KB Output is correct
3 Correct 950 ms 884 KB Output is correct
4 Correct 674 ms 756 KB Output is correct
5 Correct 572 ms 868 KB Output is correct
6 Correct 542 ms 884 KB Output is correct
7 Correct 559 ms 1004 KB Output is correct
8 Correct 3 ms 736 KB Output is correct
9 Correct 5 ms 736 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 641 ms 868 KB Output is correct
12 Correct 506 ms 992 KB Output is correct
13 Correct 453 ms 1032 KB Output is correct
14 Correct 501 ms 736 KB Output is correct
15 Correct 70 ms 756 KB Output is correct
16 Correct 88 ms 756 KB Output is correct
17 Correct 122 ms 1112 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 937 ms 756 KB Output is correct
2 Correct 840 ms 736 KB Output is correct
3 Correct 662 ms 1012 KB Output is correct
4 Correct 3 ms 916 KB Output is correct
5 Correct 5 ms 756 KB Output is correct
6 Correct 2 ms 868 KB Output is correct
7 Correct 672 ms 756 KB Output is correct
8 Correct 1001 ms 756 KB Output is correct
9 Correct 692 ms 868 KB Output is correct
10 Correct 693 ms 996 KB Output is correct
11 Incorrect 1 ms 364 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 Correct 631 ms 1012 KB Output is correct
2 Correct 468 ms 816 KB Output is correct
3 Correct 930 ms 756 KB Output is correct
4 Correct 703 ms 1068 KB Output is correct
5 Correct 607 ms 736 KB Output is correct
6 Correct 462 ms 956 KB Output is correct
7 Correct 551 ms 1012 KB Output is correct
8 Correct 3 ms 756 KB Output is correct
9 Correct 5 ms 736 KB Output is correct
10 Correct 1 ms 736 KB Output is correct
11 Incorrect 5 ms 492 KB Invalid labels (duplicates values). scenario=0, label=3
12 Halted 0 ms 0 KB -