oj.uz

Submission #52234

# Submission time Handle Problem Language Result Execution time Memory
52234 2018-06-25T05:43:46 Z ics0503 Factories (JOI14_factories) C++17
100 / 100
 6914 ms 228692 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 24952 KB Output is correct
2 Correct 1557 ms 34584 KB Output is correct
3 Correct 1498 ms 34584 KB Output is correct
4 Correct 1421 ms 34872 KB Output is correct
5 Correct 1200 ms 34872 KB Output is correct
6 Correct 1198 ms 34872 KB Output is correct
7 Correct 1468 ms 34872 KB Output is correct
8 Correct 1394 ms 34872 KB Output is correct
9 Correct 1174 ms 35012 KB Output is correct
10 Correct 1162 ms 35012 KB Output is correct
11 Correct 1881 ms 35012 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35012 KB Output is correct
2 Correct 3079 ms 190872 KB Output is correct
3 Correct 4073 ms 194596 KB Output is correct
4 Correct 2312 ms 194596 KB Output is correct
5 Correct 3900 ms 223500 KB Output is correct
6 Correct 4537 ms 223500 KB Output is correct
7 Correct 4688 ms 223500 KB Output is correct
8 Correct 2503 ms 223500 KB Output is correct
9 Correct 3884 ms 223500 KB Output is correct
10 Correct 4595 ms 223500 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 24952 KB Output is correct
2 Correct 1557 ms 34584 KB Output is correct
3 Correct 1498 ms 34584 KB Output is correct
4 Correct 1421 ms 34872 KB Output is correct
5 Correct 1200 ms 34872 KB Output is correct
6 Correct 1198 ms 34872 KB Output is correct
7 Correct 1468 ms 34872 KB Output is correct
8 Correct 1394 ms 34872 KB Output is correct
9 Correct 1174 ms 35012 KB Output is correct
10 Correct 1162 ms 35012 KB Output is correct
11 Correct 1881 ms 35012 KB Output is correct
12 Correct 25 ms 35012 KB Output is correct
13 Correct 3079 ms 190872 KB Output is correct
14 Correct 4073 ms 194596 KB Output is correct
15 Correct 2312 ms 194596 KB Output is correct
16 Correct 3900 ms 223500 KB Output is correct
17 Correct 4537 ms 223500 KB Output is correct
18 Correct 4688 ms 223500 KB Output is correct
19 Correct 2503 ms 223500 KB Output is correct
20 Correct 3884 ms 223500 KB Output is correct
21 Correct 4595 ms 223500 KB Output is correct
22 Correct 5729 ms 223500 KB Output is correct
23 Correct 5364 ms 223500 KB Output is correct
24 Correct 6394 ms 223500 KB Output is correct
25 Correct 6210 ms 223500 KB Output is correct
26 Correct 6798 ms 223500 KB Output is correct
27 Correct 5593 ms 228692 KB Output is correct
28 Correct 4342 ms 228692 KB Output is correct
29 Correct 6719 ms 228692 KB Output is correct
30 Correct 6914 ms 228692 KB Output is correct
31 Correct 6759 ms 228692 KB Output is correct
32 Correct 3025 ms 228692 KB Output is correct
33 Correct 2540 ms 228692 KB Output is correct
34 Correct 3521 ms 228692 KB Output is correct
35 Correct 3375 ms 228692 KB Output is correct
36 Correct 3856 ms 228692 KB Output is correct
37 Correct 3749 ms 228692 KB Output is correct