oj.uz

답안 #35357

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
35357 2017-11-20T16:15:25 Z UncleGrandpa925 공장들 (JOI14_factories) C++14
100 / 100
 5859 ms 300024 KB 
#ifndef UncleGrandpa
#include "factories.h"
#endif

#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define bit(x,y) ((x>>y)&1LL)
#define N 500005
ostream& operator << (ostream &os, vector<int>&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << sp;
	return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
	cout << x.fi << sp << x.se << sp;
	return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << endl;
	return os;
}
#define ll long long
vector<vector<pair<int, int> > > a(N);
ll n;

ll dis[N];
int Time = 0;
int depth[N];
pair<int, int> tour[2 * N], rmq[2 * N][22];
int par[N], sta[N], en[N];

void dfs(int u, int p) {
	tour[++Time] = make_pair(depth[u], u); sta[u] = Time;
	par[u] = p;
	for (int i = 0; i < a[u].size(); i++)  {
		int v = a[u][i].fi; int w = a[u][i].se;
		if (v == p) continue;
		depth[v] = depth[u] + 1, dis[v] = dis[u] + w; dfs(v, u);
	}
	tour[++Time] = make_pair(depth[u], u); en[u] = Time;
}

void build_rmq() {
	for (int i = 1; i <= Time; ++i)
		rmq[i][0] = tour[i];
	for (int j = 1; (1 << j) <= Time; ++j)
		for (int i = 1; i + (1 << j) - 1 <= Time; ++i)
			rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
}

void makelca() {
	dfs(1, 1);
	build_rmq();
}

int lca(int u, int v) {
	if (sta[v] < sta[u]) swap(u, v);
	if (en[u] >= en[v]) return u;
	int dist = log2(sta[v] - en[u] + 1);
	pair<int, int> ans = min(rmq[en[u]][dist], rmq[sta[v] - (1 << dist) + 1][dist]);
	return par[ans.second];
}

ll lcadis(int u, int v) {
	return abs(dis[u] - dis[v]);
}

ll distance(int u, int v) {
	int p = lca(u, v);
	return dis[u] - dis[p] + dis[v] - dis[p];
}


void Init(int _N, int _A[], int _B[], int _D[]) {
	n = _N;
	for (int i = 0; i < n; i++) {
		int u = _A[i]; int v = _B[i]; int c = _D[i];
		u++; v++;
		a[u].push_back(mp(v, c));
		a[v].push_back(mp(u, c));
	}
	makelca();
}

vector < vector<pair<int, ll> > > b(N);
vector<int> allVertex;
stack<int> st;
bool byEuler(int u, int v) {
	return sta[u] < sta[v];
}

void makeEdge() {
	sort(allVertex.begin(), allVertex.end(), byEuler);
	int sz = allVertex.size();
	for (int i = 1; i < sz; i++) {
		int u = allVertex[i - 1];
		int v = allVertex[i];
		int p = lca(u, v);
		allVertex.push_back(p);
	}
	sort(allVertex.begin(), allVertex.end(), byEuler);
	allVertex.resize(distance(allVertex.begin(), unique(allVertex.begin(), allVertex.end())));
	while (!st.empty()) st.pop();
	for (int i = 0; i < allVertex.size(); i++) {
		int u = allVertex[i];
		while (!st.empty() && en[st.top()] < sta[u]) st.pop();
		if (st.empty()) {
			st.push(u); continue;
		}
		if (st.top() == u) continue;
		b[st.top()].push_back(mp(u, lcadis(st.top(), u)));
		b[u].push_back(mp(st.top(), lcadis(st.top(), u)));
		st.push(u);
	}
}

bool mark[N];
ll dist[N];

priority_queue<pair<ll, ll> , vector<pair<ll, ll> >, greater<pair<ll, ll> > > pq;
ll Query(int S, int X[], int T, int Y[]) {
	while (!pq.empty()) pq.pop(); allVertex.clear();
	for (ll i = 0; i < S; i++) X[i]++, allVertex.push_back(X[i]);
	for (ll i = 0; i < T; i++) Y[i]++, allVertex.push_back(Y[i]);
	makeEdge();
	for (auto u : allVertex) dist[u] = 1e18;
	for (ll i = 0; i < S; i++) pq.push(mp(0, X[i])), dist[X[i]] = 0;
	for (ll i = 0; i < T; i++) mark[Y[i]] = true;
	ll ret = 1e18;
	while (!pq.empty()) {
		ll u = pq.top().se; ll d = pq.top().fi; pq.pop();
		if (d != dist[u]) continue;
		if (mark[u]) {
			ret = d; break;
		}
		for (ll i = 0; i < b[u].size(); i++) {
			ll v = b[u][i].fi; ll w = b[u][i].se;
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				pq.push(mp(dist[v], v));
			}
		}
	}
	for (ll i = 0; i < T; i++) mark[Y[i]] = false;
	for (auto u : allVertex) b[u].clear();
	return ret;
}


#ifdef UncleGrandpa
#define MAX_N          500000
#define MAX_Q          100000
#define MAX_SUM_ST    1000000
#define MAX_VALUE  1000000000

static int _N, _Q;
static int _A[MAX_N], _B[MAX_N], _D[MAX_N];
static int _S[MAX_N];
static int _T[MAX_N];
static int _X[MAX_SUM_ST];
static int _Y[MAX_SUM_ST];

static int _Qx[MAX_N];
static int _Qy[MAX_N];
#endif

#ifdef UncleGrandpa
int main() {
#ifdef in1code
	freopen("1test.inp", "r", stdin);
#endif
	int i, j, k;
	int STop, TTop;

	if (2 != scanf("%d%d", &_N, &_Q)) {
		fprintf(stderr, "error: cannot read _N and _Q.\n");
		exit(1);
	}
	if (!(2 <= _N && _N <= MAX_N)) {
		fprintf(stderr, "error: _N is out of bounds.\n");
		exit(1);
	}
	if (!(1 <= _Q && _Q <= MAX_Q)) {
		fprintf(stderr, "error: _Q is out of bounds.\n");
		exit(1);
	}
	for (i = 0; i < _N - 1; ++i) {
		if (1 != scanf("%d", &_A[i])) {
			fprintf(stderr, "error: cannot read _A[%d].\n", i);
			exit(1);
		}
		if (!(0 <= _A[i] && _A[i] <= _N - 1)) {
			fprintf(stderr, "error: _A[%d] is out of bounds.\n", i);
			exit(1);
		}
		if (1 != scanf("%d", &_B[i])) {
			fprintf(stderr, "error: cannot read _B[%d].\n", i);
			exit(1);
		}
		if (!(0 <= _B[i] && _B[i] <= _N - 1)) {
			fprintf(stderr, "error: _B[%d] is out of bounds.\n", i);
			exit(1);
		}
		if (_A[i] == _B[i]) {
			fprintf(stderr, "error: _B[%d] is equal to _A[%d].\n", i, i);
			exit(1);
		}
		if (1 != scanf("%d", &_D[i])) {
			fprintf(stderr, "error: cannot read _D[%d].\n", i);
			exit(1);
		}
		if (!(1 <= _D[i] && _D[i] <= MAX_VALUE)) {
			fprintf(stderr, "error: _D[%d] is out of bounds.\n", i);
			exit(1);
		}
	}

	STop = 0;
	TTop = 0;

	for (j = 0; j < _Q; ++j) {
		if (2 != scanf("%d%d", &_S[j], &_T[j])) {
			fprintf(stderr, "error: cannot read L[%d] and R[%d].\n", j, j);
			exit(1);
		}

		if (STop + _S[j] > MAX_SUM_ST) {
			fprintf(stderr, "error: _S[0] + _S[1] + ... + _S[%d] is out of bounds.\n", j);
			exit(1);
		}

		if (TTop + _T[j] > MAX_SUM_ST) {
			fprintf(stderr, "error: _T[0] + _T[1] + ... + _T[%d] is out of bounds.\n", j);
			exit(1);
		}

		for (k = 0; k < _S[j]; ++k, ++STop) {
			if (1 != scanf("%d", &_X[STop])) {
				fprintf(stderr, "error: cannot read _X[%d][%d].\n", j, k);
				exit(1);
			}

			if (!(0 <= _X[STop] && _X[STop] <= _N - 1)) {
				fprintf(stderr, "error: cannot read _X[%d][%d].\n", j, k);
				exit(1);
			}
		}

		for (k = 0; k < _T[j]; ++k, ++TTop) {
			if (1 != scanf("%d", &_Y[TTop])) {
				fprintf(stderr, "error: cannot read _Y[%d][%d].\n", j, k);
				exit(1);
			}

			if (!(0 <= _Y[TTop] && _Y[TTop] <= _N - 1)) {
				fprintf(stderr, "error: cannot read _Y[%d][%d].\n", j, k);
				exit(1);
			}
		}
	}

	STop = 0;
	TTop = 0;
	Init(_N, _A, _B, _D);

	for (j = 0; j < _Q; ++j) {
		for (k = 0; k < _S[j]; k++) {
			_Qx[k] = _X[STop++];
		}
		for (k = 0; k < _T[j]; k++) {
			_Qy[k] = _Y[TTop++];
		}

		printf("%lld\n", Query(_S[j], _Qx, _T[j], _Qy));
	}
	return 0;
}
#endif

Compilation message

factories.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<int>&)':
factories.cpp:15:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << sp;
                    ^
factories.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<int, int> >&)':
factories.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                    ^
factories.cpp: In function 'void dfs(int, int)':
factories.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a[u].size(); i++)  {
                    ^
factories.cpp: In function 'void makeEdge()':
factories.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < allVertex.size(); i++) {
                    ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:140:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (ll i = 0; i < b[u].size(); i++) {
                    ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 243684 KB Output is correct
2 Correct 1363 ms 244088 KB Output is correct
3 Correct 1413 ms 244080 KB Output is correct
4 Correct 1369 ms 244276 KB Output is correct
5 Correct 1303 ms 244164 KB Output is correct
6 Correct 1033 ms 244040 KB Output is correct
7 Correct 1483 ms 244080 KB Output is correct
8 Correct 1389 ms 244080 KB Output is correct
9 Correct 1316 ms 244160 KB Output is correct
10 Correct 1039 ms 244040 KB Output is correct
11 Correct 1373 ms 244080 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 243552 KB Output is correct
2 Correct 2776 ms 276288 KB Output is correct
3 Correct 3096 ms 279688 KB Output is correct
4 Correct 2583 ms 277124 KB Output is correct
5 Correct 2786 ms 299468 KB Output is correct
6 Correct 3723 ms 279628 KB Output is correct
7 Correct 2536 ms 251452 KB Output is correct
8 Correct 1966 ms 250820 KB Output is correct
9 Correct 1643 ms 253788 KB Output is correct
10 Correct 2159 ms 251248 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5859 ms 286468 KB Output is correct
2 Correct 5413 ms 286296 KB Output is correct
3 Correct 5809 ms 289088 KB Output is correct
4 Correct 5519 ms 288908 KB Output is correct
5 Correct 5186 ms 283124 KB Output is correct
6 Correct 4739 ms 300024 KB Output is correct
7 Correct 4035 ms 282788 KB Output is correct
8 Correct 5093 ms 281952 KB Output is correct
9 Correct 4789 ms 281436 KB Output is correct
10 Correct 4926 ms 281728 KB Output is correct
11 Correct 2549 ms 256316 KB Output is correct
12 Correct 2176 ms 256380 KB Output is correct
13 Correct 3046 ms 252284 KB Output is correct
14 Correct 2709 ms 252004 KB Output is correct
15 Correct 2679 ms 252400 KB Output is correct
16 Correct 2553 ms 252396 KB Output is correct