oj.uz

Submission #52212

# Submission time Handle Problem Language Result Execution time Memory
52212 2018-06-25T04:58:43 Z 이창수(#1964) Factories (JOI14_factories) C++11
33 / 100
 6000 ms 223660 KB 
#include "factories.h"
#include<vector>
#include<algorithm>
using namespace std;
struct xy { long long x, y; };
struct gg { long long 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(long long w,long long 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++) {
		long long 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;
	long long 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);
	an = unique(ALL, ALL + an) - ALL;
	vector<long long>stk;
	sort(ALL, ALL + an, sort_st);
	stk.push_back(ALL[0]);
	for (i = 1; i < an; i++) {
		long long 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++)E[ALL[i]].clear(), 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(long long int, long long 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:15: warning: unused variable 'j' [-Wunused-variable]
  long long i, j; ln = an = 0;
               ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 25080 KB Output is correct
2 Correct 1645 ms 34600 KB Output is correct
3 Correct 1686 ms 34748 KB Output is correct
4 Correct 1554 ms 34876 KB Output is correct
5 Correct 1222 ms 35184 KB Output is correct
6 Correct 1201 ms 35184 KB Output is correct
7 Correct 1628 ms 35184 KB Output is correct
8 Correct 1543 ms 35184 KB Output is correct
9 Correct 1328 ms 35184 KB Output is correct
10 Correct 1229 ms 35184 KB Output is correct
11 Correct 1653 ms 35184 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 35184 KB Output is correct
2 Correct 3150 ms 190996 KB Output is correct
3 Correct 4185 ms 194724 KB Output is correct
4 Correct 2438 ms 194724 KB Output is correct
5 Correct 3765 ms 223660 KB Output is correct
6 Correct 4379 ms 223660 KB Output is correct
7 Correct 4605 ms 223660 KB Output is correct
8 Correct 2449 ms 223660 KB Output is correct
9 Correct 3711 ms 223660 KB Output is correct
10 Correct 4638 ms 223660 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 25080 KB Output is correct
2 Correct 1645 ms 34600 KB Output is correct
3 Correct 1686 ms 34748 KB Output is correct
4 Correct 1554 ms 34876 KB Output is correct
5 Correct 1222 ms 35184 KB Output is correct
6 Correct 1201 ms 35184 KB Output is correct
7 Correct 1628 ms 35184 KB Output is correct
8 Correct 1543 ms 35184 KB Output is correct
9 Correct 1328 ms 35184 KB Output is correct
10 Correct 1229 ms 35184 KB Output is correct
11 Correct 1653 ms 35184 KB Output is correct
12 Correct 26 ms 35184 KB Output is correct
13 Correct 3150 ms 190996 KB Output is correct
14 Correct 4185 ms 194724 KB Output is correct
15 Correct 2438 ms 194724 KB Output is correct
16 Correct 3765 ms 223660 KB Output is correct
17 Correct 4379 ms 223660 KB Output is correct
18 Correct 4605 ms 223660 KB Output is correct
19 Correct 2449 ms 223660 KB Output is correct
20 Correct 3711 ms 223660 KB Output is correct
21 Correct 4638 ms 223660 KB Output is correct
22 Correct 5749 ms 223660 KB Output is correct
23 Correct 5366 ms 223660 KB Output is correct
24 Execution timed out 6086 ms 223660 KB Time limit exceeded
25 Halted 0 ms 0 KB -