oj.uz

Submission #52216

# Submission time Handle Problem Language Result Execution time Memory
52216 2018-06-25T05:05:12 Z 이창수(#1964) Factories (JOI14_factories) C++11
33 / 100
 6000 ms 250984 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 60 ms 25172 KB Output is correct
2 Correct 1449 ms 40008 KB Output is correct
3 Correct 1627 ms 49592 KB Output is correct
4 Correct 1548 ms 59212 KB Output is correct
5 Correct 1362 ms 62392 KB Output is correct
6 Correct 1128 ms 62392 KB Output is correct
7 Correct 1674 ms 62392 KB Output is correct
8 Correct 1525 ms 62392 KB Output is correct
9 Correct 1226 ms 62600 KB Output is correct
10 Correct 1213 ms 62600 KB Output is correct
11 Correct 1537 ms 62600 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 62600 KB Output is correct
2 Correct 2978 ms 218508 KB Output is correct
3 Correct 4112 ms 222008 KB Output is correct
4 Correct 2270 ms 222008 KB Output is correct
5 Correct 3800 ms 250984 KB Output is correct
6 Correct 4556 ms 250984 KB Output is correct
7 Correct 4677 ms 250984 KB Output is correct
8 Correct 2525 ms 250984 KB Output is correct
9 Correct 3686 ms 250984 KB Output is correct
10 Correct 4907 ms 250984 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 25172 KB Output is correct
2 Correct 1449 ms 40008 KB Output is correct
3 Correct 1627 ms 49592 KB Output is correct
4 Correct 1548 ms 59212 KB Output is correct
5 Correct 1362 ms 62392 KB Output is correct
6 Correct 1128 ms 62392 KB Output is correct
7 Correct 1674 ms 62392 KB Output is correct
8 Correct 1525 ms 62392 KB Output is correct
9 Correct 1226 ms 62600 KB Output is correct
10 Correct 1213 ms 62600 KB Output is correct
11 Correct 1537 ms 62600 KB Output is correct
12 Correct 27 ms 62600 KB Output is correct
13 Correct 2978 ms 218508 KB Output is correct
14 Correct 4112 ms 222008 KB Output is correct
15 Correct 2270 ms 222008 KB Output is correct
16 Correct 3800 ms 250984 KB Output is correct
17 Correct 4556 ms 250984 KB Output is correct
18 Correct 4677 ms 250984 KB Output is correct
19 Correct 2525 ms 250984 KB Output is correct
20 Correct 3686 ms 250984 KB Output is correct
21 Correct 4907 ms 250984 KB Output is correct
22 Execution timed out 6016 ms 250984 KB Time limit exceeded
23 Halted 0 ms 0 KB -