oj.uz

Submission #427310

# Submission time Handle Problem Language Result Execution time Memory
427310 2021-06-14T14:12:41 Z AugustinasJucas Stations (IOI20_stations) C++14
10 / 100
 1190 ms 724 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();
	}
	
	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 328 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 448 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 4 ms 328 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 1190 ms 528 KB Output is correct
2 Correct 798 ms 516 KB Output is correct
3 Correct 817 ms 516 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 728 ms 644 KB Output is correct
8 Correct 1091 ms 400 KB Output is correct
9 Correct 959 ms 528 KB Output is correct
10 Correct 958 ms 400 KB Output is correct
11 Correct 8 ms 596 KB Output is correct
12 Correct 8 ms 604 KB Output is correct
13 Correct 6 ms 572 KB Output is correct
14 Correct 4 ms 596 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 576 ms 528 KB Output is correct
17 Correct 469 ms 516 KB Output is correct
18 Correct 855 ms 528 KB Output is correct
19 Correct 633 ms 604 KB Output is correct
20 Correct 783 ms 400 KB Output is correct

Subtask #5
0 / 61.0

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