oj.uz

Submission #317506

# Submission time Handle Problem Language Result Execution time Memory
317506 2020-10-30T00:25:13 Z rqi Stations (IOI20_stations) C++14
0 / 100
 942 ms 1568 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pi;

#define pb push_back
#define bk back()
#define mp make_pair
#define f first
#define s second
#define all(x) begin(x), end(x)

const int mx = 1005;
vi adj[mx];
int depth[mx];
pi rang[mx];
int cnt = 0;

vi labels;

void genET(int node, int prv = -1, int d = 0){
	depth[node] = d;
	cnt++;
	rang[node].f = rang[node].s = cnt;
	for(auto u: adj[node]){
		if(u == prv) continue;
		genET(u, node, d+1);
		cnt++; 
		rang[node].s = cnt;
	}
	if(depth[node] % 2 == 0){
		labels[node] = rang[node].f;
	}
	else labels[node] = rang[node].s;
}

vi label(int n, int k, vi u, vi v) {
	for(int i = 0; i < n; i++){
		adj[i].clear();
	}

	for(int i = 0; i < n-1; i++){
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
	}
	labels = vi(n);

	genET(0);

	map<int, int> m;
	for(auto u: labels) m[u];
	cnt = 0;
	for(auto &u: m){
		u.s = cnt++;
	} 
	for(auto &u: labels) u = m[u];
	return labels;
}

int find_next_station(int s, int t, vi c) {
	bool typ = 0;
	if(c[0] < s) typ = 1;

	
	if(typ == 0){
		sort(all(c));
		if(t < s) return c.bk;
		for(auto u: c) if(u >= t) return u;
	}
	else{
		sort(c.rbegin(), c.rend());
		if(t > s) return c.bk;
		for(auto u: c) if(u <= t) return u;
	}
	assert(0 == 1);
	return -1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 942 ms 1008 KB Output is correct
2 Correct 780 ms 876 KB Output is correct
3 Runtime error 2 ms 1296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 1568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -