2015 상하 이 지역 전 D 문제 좌 편 수 + 트 리 DP

2677 단어 ACM데이터 구조
약 반 주일 의 시간 을 들 여 마침내 만들어 냈 다. 이 문 제 는 세부 사항 이 매우 많다. 주석 이나 아이디어 같은 거 나중에 보충 해 주세요. 지금 너무 힘 들 어 요!
제목 링크: 클릭 하여 링크 열기
코드 는 다음 과 같 습 니 다:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define rep(i, n) for(int i=0; i P;
const int INF = 0x7fffffff;
const int MAX_N = 2e5 + 5;
const int MAX_V = 0;
const int MAX_M = 0;
const int MAX_Q = 0;

int l[MAX_N], r[MAX_N], dist[MAX_N];
int N, M;
P query[MAX_N], ban[MAX_N];
int par[MAX_N], in[MAX_N];
vector
 s;

int merge(int a, int b) {
	if (!a) return b;
	if (!b) return a;
	if (query[a].first > query[b].first)  swap(a, b);
	r[a] = merge(r[a], b);
	if (dist[r[a]] > dist[l[a]]) swap(l[a], r[a]);
	if (!r[a]) dist[a] = 0;
	else dist[a] = dist[r[a]] + 1;
	return a;
}
struct node {
	int qe, h, out, in;
}nd[MAX_N];

int root(int x) {
	return par[x] == x ? x : par[x] = root(par[x]);
}

void init() {
	memset(l, 0, sizeof l);
	memset(r, 0, sizeof r);
	memset(dist, 0, sizeof dist);

	Rep(i, N) {
		par[i] = i;
		nd[i].h = nd[i].in = nd[i].out = nd[i].qe = 0;
	}
	Rep(i, M) nd[in[i]].qe = merge(nd[in[i]].qe, i);
}

void get_up(int id, int he) {
	int in_max=0, out_max=0, tmp = 0;
	s.clear();
	while (nd[id].qe && query[nd[id].qe].first < he) {
		if (query[nd[id].qe].second == 0) in_max++;
		s.push_back(query[nd[id].qe]);
		nd[id].qe = merge(l[nd[id].qe], r[nd[id].qe]);
	}
	tmp = out_max = in_max;
	for (int i = 0; i < s.size(); i++) {
		if (i && s[i].first != s[i - 1].first) {
			out_max = max(tmp, out_max);
		}
		s[i].second == 0 ? tmp-- : tmp++;
	}
	out_max = max(out_max, tmp);
	nd[id].in = max(nd[id].in + in_max, nd[id].out + out_max);
	nd[id].out += tmp;
	nd[id].h = he;
}

void Merge(int p1, int p2, int he) {
	p1 = root(p1);
	p2 = root(p2);
	if(nd[p1].h> T;
	while (T--) {
		cin >> N >> M;
		Rep(i, N - 1) {
			scanf("%d", &ban[i].first);
			ban[i].second = i;
		}
		Rep(i, M) {
			scanf("%d%d%d", &in[i], &query[i].first, &query[i].second);
		}
		cout << "Case #" << ++Case << ": ";
		solve();
	}
}
TCP 연결 구축 시리즈 - 연결 요청 블록
이코테-chapter9: 최단 경로-다익스트라 최단 경로 알고리즘

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage