oj.uz

Submission #427313

# Submission time Handle Problem Language Result Execution time Memory
427313 2021-06-14T14:14:13 Z AugustinasJucas Stations (IOI20_stations) C++14
10 / 100
 1339 ms 664 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int dydis = 1000;
vector<int> gr[dydis];
int enter[dydis];
int leave[dydis];
vector<int> ret (dydis);
int dbInd = 0;
void dfs(int v, int came){
	enter[v] = dbInd++;
	for(auto x : gr[v]){
		if(x == came) continue;
		dfs(x, v);
	}
	leave[v] = dbInd;
	ret[v] = enter[v] * dydis + leave[v] - 1;
	//cout << "enter " << v << " - " << enter[v] << ", o leave " << leave[v]-1 << endl;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	for(int i = 0; i < n; i++){
		gr[i].clear();
		gr[i].clear();
	}
	dbInd = 0;
	for(int i = 0; i < n-1; i++){
		gr[u[i]].push_back(v[i]);
		gr[v[i]].push_back(u[i]);
	}
	dfs(0, -1);
	ret.resize(n);
	
	return ret;
}

int find_next_station(int s, int t, vector<int> c) {
	int enterS = s / 1000;
	int leaveS = s % 1000;
	int enterT = t / 1000;
	int leaveT = t % 1000;
//	cout << "kitas einant is " << s << " i " << t << " yra:\n";
	if(enterS <= enterT && leaveT <= leaveS){
	//	cout << enterS << " yra " << enterT << " tevas\n";
		for(auto x : c){
			int e = x / 1000;
			int l = x % 1000;
			if(e <= enterT && leaveT <= l && !(e <= enterS && leaveS <= l)){
		//		cout << "ret " << x << endl << endl;
				return x;
			}
		}
	}else{ // eisiu aukstyn
		for(auto x : c){
			int e = x / 1000;
			int l = x % 1000;
			if(e <= enterS && leaveS <= l){
			//	cout << "ret " << x << endl << endl;
				return x;
			}
		}
	}
	return c[0];
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 312 KB Invalid labels (duplicates values). scenario=1, label=0
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1339 ms 656 KB Output is correct
2 Correct 724 ms 400 KB Output is correct
3 Correct 747 ms 664 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 6 ms 464 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 675 ms 552 KB Output is correct
8 Correct 1130 ms 400 KB Output is correct
9 Correct 830 ms 528 KB Output is correct
10 Correct 723 ms 428 KB Output is correct
11 Correct 7 ms 596 KB Output is correct
12 Correct 7 ms 596 KB Output is correct
13 Correct 5 ms 596 KB Output is correct
14 Correct 5 ms 468 KB Output is correct
15 Correct 2 ms 560 KB Output is correct
16 Correct 709 ms 400 KB Output is correct
17 Correct 874 ms 520 KB Output is correct
18 Correct 750 ms 528 KB Output is correct
19 Correct 700 ms 516 KB Output is correct
20 Correct 684 ms 400 KB Output is correct

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 328 KB Invalid labels (duplicates values). scenario=1, label=0
2 Halted 0 ms 0 KB -