oj.uz

Submission #377833

# Submission time Handle Problem Language Result Execution time Memory
377833 2021-03-15T08:25:24 Z autumn_eel Stations (IOI20_stations) C++14
10 / 100
 1093 ms 1060 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;
static int cnt=0;

void dfs(int v,int p){
	int L=cnt++;
	for(int u:E[v]){
		if(u==p)continue;
		dfs(u,v);
	}
	int R=cnt;
	labels[v]=L*1000+R;
}

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);
	cnt=0;
	rep(i,n-1){
		E[u[i]].push_back(v[i]);
		E[v[i]].push_back(u[i]);
	}
	dfs(0,-1);
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	int sl=s/1000,sr=s%1000;
	int tl=t/1000,tr=t%1000;
	for(int u:c){
		int ul=u/1000,ur=u%1000;
		if(ul<=sl&&sr<=ur)continue;
		if(ul<=tl&&tr<=ur)return u;
	}
	for(int u:c){
		int ul=u/1000,ur=u%1000;
		if(ul<=sl&&sr<=ur)return u;
	}
	return -1;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1017 ms 1060 KB Output is correct
2 Correct 740 ms 756 KB Output is correct
3 Correct 650 ms 756 KB Output is correct
4 Correct 3 ms 876 KB Output is correct
5 Correct 4 ms 796 KB Output is correct
6 Correct 1 ms 736 KB Output is correct
7 Correct 681 ms 756 KB Output is correct
8 Correct 1093 ms 868 KB Output is correct
9 Correct 801 ms 756 KB Output is correct
10 Correct 745 ms 736 KB Output is correct
11 Correct 6 ms 868 KB Output is correct
12 Correct 7 ms 876 KB Output is correct
13 Correct 4 ms 736 KB Output is correct
14 Correct 6 ms 756 KB Output is correct
15 Correct 2 ms 756 KB Output is correct
16 Correct 528 ms 756 KB Output is correct
17 Correct 612 ms 892 KB Output is correct
18 Correct 587 ms 884 KB Output is correct
19 Correct 583 ms 748 KB Output is correct
20 Correct 591 ms 736 KB Output is correct

Subtask #5
0 / 61.0

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