oj.uz

답안 #1067326

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1067326 2024-08-20T14:53:14 Z Lalic 기지국 (IOI20_stations) C++17
0 / 100
 629 ms 988 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(). x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

const int INF = 0x3f3f3f3f;

void build(int ver, int prev, vector<int>& labels, bool isMax, int& cnt, vector<vector<int>>& adj, vector<int>& submin, vector<int>& submax){
	if(prev!=-1 && (int)adj[ver].size()==1){
		labels[ver]=cnt;
		submin[ver]=submax[ver]=cnt;
		cnt++;
		return;
	}
	
	int mx=-INF, mn=INF;
	for(auto u : adj[ver]){
		if(u==prev) continue;
		build(u, ver, labels, !isMax, cnt, adj, submin, submax);
		mx=max(mx, submax[u]);
		mn=min(mn, submin[u]);
	}
	
	if(isMax){
		labels[ver]=submax[ver]=mx+1;
		if(mx+1>=cnt) cnt=mx+2;
	}
	else
		labels[ver]=submin[ver]=mn-1;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);
	vector<vector<int>> adj(n);
	vector<int> submin(n), submax(n);
	
	for(int i=0;i<n-1;i++){
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
	}
	
	int aux=0;
	build(1, -1, labels, 0, aux, adj, submin, submax);
	
	vector<pii> proc;
	for(int i=0;i<n;i++) proc.pb({labels[i], i});
	
	sort(all(proc));
	
	for(int i=0;i<n;i++) labels[proc[i].se]=i;
	
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	sort(all(c));
	
	if(c[0]<s){
		if(t>s || t<c[1]) return c[0];
		for(int i=(int)c.size()-1;i>=0;i--)
			if(t>=c[i]) return c[i];
	}
	else{
		reverse(all(c));
		if(t<s || t>c[1]) return c[0];
		for(int i=(int)c.size()-1;i>=0;i--)
			if(t<=c[i]) return c[i];
	}
	
	return -1;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 384 ms 988 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 310 ms 684 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 355 ms 940 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 629 ms 684 KB Output is correct
2 Correct 435 ms 684 KB Output is correct
3 Incorrect 422 ms 684 KB Wrong query response.
4 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 409 ms 940 KB Wrong query response.
2 Halted 0 ms 0 KB -