Submission #52234

#	Time	Username	Problem	Language	Result	Execution time	Memory
52234		ics0503	Factories (JOI14_factories)	C++17	100 / 100	6914 ms	228692 KiB

factories

#include "factories.h"
#include<vector>
#include<algorithm>
using namespace std;
struct xy { long long x, y; };
struct gg { int w, s, e; };
bool sort_y(xy a, xy b) {
	if (a.y != b.y)return a.y < b.y;
	return a.x < b.x;
}
vector<xy>edge[515151];
long long W[515151], ST[515151],EN[515151], Dist[515151], Depth[515151], cnt = 0;
long long par[515151][21];
bool sort_st(long long a, long long b) {
	if (ST[a] != ST[b])return ST[a] < ST[b];
	return EN[a] > EN[b];
}
void dfs(long long w, long long bef,long long depth,long long dist) {
	Depth[w] = depth;
	Dist[w] = dist;
	ST[w] = cnt;  W[w] = cnt++;
	par[w][0] = bef;
	for (long long i = 0; par[w][i] != -1; i++) par[w][i + 1] = par[par[w][i]][i];
	for (long long i = 0; i < edge[w].size(); i++) if (bef != edge[w][i].x){
		dfs(edge[w][i].x, w, depth+1, dist + edge[w][i].y);
	}
	EN[w] = cnt - 1;
}
void Init(int N, int A[], int B[], int D[]) {
	long long i, j;
	for (i = 0; i < N-1; i++) {
		long long s = A[i], e = B[i], w = D[i];
		edge[s].push_back({ e,w }); edge[e].push_back({ s,w });
	}
	for (i = 0; i < N; i++)for (j = 0; j < 20; j++)par[i][j] = -1;
	dfs(0, -1, 0, 0);
}
xy L[512121]; long long ln;
gg Q[515151];
long long ALL[515151], an;
void go(long long &x, long long y) { for (long long i = 0; i < 20; i++)if (y&(1 << i))x = par[x][i]; }
long long LCA(long long a, long long b) {
	if (Depth[a] > Depth[b])go(a, Depth[a] - Depth[b]);
	if (Depth[a] < Depth[b])go(b, Depth[b] - Depth[a]);
	if (a == b)return a;
	for (long long i = 19; i >= 0; i--)if (par[a][i] != par[b][i])a = par[a][i], b = par[b][i];
	return par[a][0];
}
long long P[515151];
vector<xy>E[515151];
long long D[515151], F[515151], CR[515151];
long long res;
long long min(long long a, long long b) { if (a < b)return a; return b; }
void DFS(int w,int bef) {
	D[w] = F[w] = 1e18;
	if (CR[w] == 1)D[w] = 0;
	if (CR[w] == 2)F[w] = 0;
	for (long long i = 0; i < E[w].size(); i++) {
		int nxt = E[w][i].x;
		if (nxt == bef)continue;
		DFS(nxt, w);
		D[w] = min(D[w], D[nxt] + E[w][i].y);
		F[w] = min(F[w], F[nxt] + E[w][i].y);
	}
	res = min(res, D[w] + F[w]);
}
long long Query(int S, int X[], int T, int Y[]){
	res = 1e18;
	int i, j; ln = an = 0;
	for (i = 0; i < S; i++)L[ln++] = { X[i],W[X[i]] },ALL[an++] = X[i], CR[X[i]] = 1;
	for (i = 0; i < T; i++)L[ln++] = { Y[i],W[Y[i]] },ALL[an++] = Y[i], CR[Y[i]] = 2;
	sort(L, L + ln,sort_y);
	for (i = 0; i < ln-1; i++) ALL[an++] = LCA(L[i].x, L[i+1].x);
	sort(ALL, ALL + an, sort_st);
	an = unique(ALL, ALL + an) - ALL;
	vector<int>stk;
	stk.push_back(ALL[0]);
	for (i = 1; i < an; i++) {
		int now = ALL[i];
		while (EN[stk.back()] < ST[now])stk.pop_back();
		P[i] = stk.back();
		stk.push_back(now);
	}
	for (i = 1; i < an; i++) {
		long long s = ALL[i], e = P[i], w = Dist[s] - Dist[e];
		E[s].push_back({ e,w });
		E[e].push_back({ s,w });
	}
	DFS(ALL[0], -1);
	for (i = 0; i < an; i++) {
		while (!E[ALL[i]].empty())E[ALL[i]].pop_back();
		CR[ALL[i]] = 0;
	}
	return res;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(long long int, long long int, long long int, long long int)':
factories.cpp:24:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (long long i = 0; i < edge[w].size(); i++) if (bef != edge[w][i].x){
                        ~~^~~~~~~~~~~~~~~~
factories.cpp: In function 'void DFS(int, int)':
factories.cpp:58:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (long long i = 0; i < E[w].size(); i++) {
                        ~~^~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:69:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j; ln = an = 0;
         ^

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67