oj.uz

답안 #306960

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
306960 2020-09-26T15:14:24 Z FelixMP 기지국 (IOI20_stations) C++14
0 / 100
 3000 ms 1024 KB 
#include "stations.h"
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>

using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;

vvi al;
vi rans;
int ft = 0;

ii dfs(int v, int p, int r) {

	int cmin =  1002;
	int cmax = -1;

	for(int i=0; i < (int)al[v].size(); ++i) {
		int u = al[v][i];
		if(u == p) continue;
		ii x = dfs(u, v, !r);

		//cerr << "VISITED " << u << " returned " << x.first << " " << x.second << endl;

		cmin = min(cmin, x.first);
		cmax = max(cmax, x.second);
	}

	if(cmin == 1002) {
		rans[ft] = v;
		ft++;
		return ii(ft-1, ft-1);
	}
	else {
		if(r) {
			for(int i=ft; i > cmax+1; --i) {
				swap(rans[i], rans[i-1]);
			}
			rans[cmax+1] = v;
			ft++;
		}
		else {
			for(int i=ft; i > cmin; --i) {
				swap(rans[i], rans[i-1]);
			}
			rans[cmin] = v;
			ft++;
		}
		return ii(cmin, max(cmax, ft-1));
	}


}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	
	al = vvi(n, vi());
	for(int i=0; i < n-1; ++i) {
		al[u[i]].push_back(v[i]);
		al[v[i]].push_back(u[i]);
	}

	rans = vi(1001, -1);
	ft = 0;

	dfs(0, -1, 0);
	vi ans(n);
	/*for(int i=0; i < 1001; ++i) {
		if(rans[i] != -1) {
			cerr << "rans[" << i << "] = " << rans[i] << endl;
		}
	}*/
	for(int i=0; i < n; ++i) {
		ans[rans[i]] = i;
	}
	return ans;

}

int find_next_station(int s, int t, std::vector<int> c) {
	int m = c.size();
	if(m == 1) return c[0];
	bool ismax = true;
	for(int i=0; i < m; ++i) {
		if(s < c[i]) ismax = false;
	}
	if(ismax) {
		int minv = 1002;
		for(int i=0; i < m; ++i) minv = min(c[i], minv);
		if(t <= minv || t >= s) return minv;
		vi otc;
		for(int i=0; i < m; ++i) {
			if(c[i] != minv) otc.push_back(c[i]);
		}
		sort(otc.begin(), otc.end());
		for(int i=m-2; i > -1; --i) {
			if(t >= otc[i]) return otc[i];
		}
	}
	else {
		int maxv = -1;
		for(int i=0; i < m; ++i) maxv = max(c[i], maxv);
		if(t >= maxv || t <= s) return maxv;
		vi otc;
		for(int i=0; i < m; ++i) {
			if(c[i] != maxv) otc.push_back(c[i]);
		}
		sort(otc.begin(), otc.end());
		for(int i=0; i < m-1; ++i) {
			if(t <= otc[i]) return otc[i];
		}
	}
	while(m++) {
		m--;
	}

}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:120:1: warning: control reaches end of non-void function [-Wreturn-type]
  120 | }
      | ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3034 ms 1024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3033 ms 1024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3056 ms 1024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 868 ms 760 KB Output is correct
2 Correct 673 ms 784 KB Output is correct
3 Execution timed out 3010 ms 648 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3042 ms 1024 KB Time limit exceeded
2 Halted 0 ms 0 KB -