제출 #722515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
722515		joelgun14	기지국 (IOI20_stations)	C++17	0 / 100	820 ms	5592 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int lim = 1e5 + 5;
int subtree[lim];
bool vis[lim];
vector<int> edges[lim];
void get_subtree(int nd = 0) {
	vis[nd] = 1;
	subtree[nd] = 1;
	for(auto i : edges[nd]) {
		if(!vis[i]) {
			get_subtree(i);
			subtree[nd] += subtree[i];
		}
	}
}
vector<int> ret;
void dfs(int nd, int l, int r, bool pos) {
	vis[nd] = 1;
	assert(l <= r);
	if(!pos) {
		ret[nd] = l, ++l;
	}
	else {
		ret[nd] = r, --r;
	}
	for(auto i : edges[nd]) {
		if(!vis[i]) {
			dfs(i, l, l + subtree[i] - 1, pos ^ 1);			
			l += subtree[i];
		}
	}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	for(int i = 0; i < n - 1; ++i) {
		edges[u[i]].push_back(v[i]);
		edges[v[i]].push_back(u[i]);
	}
	get_subtree();
	ret.resize(n);
	memset(vis, 0, sizeof(vis));
	dfs(0, 0, n - 1, 0);
	// alternate tiap depth
	// ada yg node merupakan r ada yg node merupakan l
	// jadi nanti bisa cari l/r di depth tiap node
	// determine root?
	// always set root to 0 and l
	// depth 1 is set to right
	// depth 2 is set to left and so on
	// 0 child ke border kanan
	// 1 child ke border kiri
	// gimana klo border kiri/kanan conflict dengan child?
	// childnya ngalah
	// jika di l
	// maka child dan par semua di kanan
	// par otomatis merupakan yang paling besar labelnya
	// jika di r
	// maka child dan par semua di kiri
	// par otomatis merupakan yang paling kecil
	//for(auto i : ret)
	//	cout << i << " ";
	//cout << endl;
	vector<int> tmp = ret;
	return tmp;
}

int find_next_station(int s, int t, vector<int> c) {
	// cek c nya
	// kalo s 0 itu base case
	// berarti nanti cari childnya
	// kalo misal bukan, cek c nya itu lebih dari s atau semua kurang dari s
	if(s == 0) {
		// semua childnya r
		for(int i = 0; i < c.size(); ++i) {
			if(t <= c[i])
				return c[i];
		}
	}
	bool small = c[0] < s;
	if(small) {
		// if c < s berarti s ini r terus sisanya l
		// yang paling kecil itu par
		// childnya indicate left
		vector<pair<int, pair<int, int>>> seg;
		int pr = s - 1; 
		for(int i = c.size() - 1; i >= 1; --i) {
			seg.push_back(make_pair(c[i], make_pair(c[i], pr)));
			pr = c[i] - 1;
		}
		for(int i = 0; i < seg.size(); ++i) {
			if(t >= seg[i].second.first && t <= seg[i].second.second)
				return seg[i].first;
		}
		return c.front();
	}
	else {
		// s ini l sisanya r
		// yg par yang paling besar
		vector<pair<int, pair<int, int>>> seg;
		int pr = s + 1;
		for(int i = 0; i < c.size() - 1; ++i) {
			seg.push_back(make_pair(c[i], make_pair(pr, c[i])));
			pr = c[i] + 1;
		}
		for(int i = 0; i < seg.size(); ++i) {
			if(t >= seg[i].second.first && t <= seg[i].second.second)
				return seg[i].first;
		}
		return c.back();
	}
}

컴파일 시 표준 에러 (stderr) 메시지

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for(int i = 0; i < c.size(); ++i) {
      |                  ~~^~~~~~~~~~
stations.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   for(int i = 0; i < seg.size(); ++i) {
      |                  ~~^~~~~~~~~~~~
stations.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for(int i = 0; i < c.size() - 1; ++i) {
      |                  ~~^~~~~~~~~~~~~~
stations.cpp:106:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   for(int i = 0; i < seg.size(); ++i) {
      |                  ~~^~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 0 / 10
• Subtask 5: 0 / 61