oj.uz

답안 #35360

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
35360 2017-11-20T16:37:38 Z UncleGrandpa925 공장들 (JOI14_factories) C++14
100 / 100
 5566 ms 304640 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];
int lg2[2 * 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 = lg2[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 = 1; i <= 2 * N - 5; i++)lg2[i] = log2(i);
	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;

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++)
		allVertex.push_back(lca(allVertex[i - 1], allVertex[i]));
	sort(allVertex.begin(), allVertex.end(), byEuler);
	allVertex.resize(distance(allVertex.begin(), unique(allVertex.begin(), allVertex.end())));
	stack<int> st;
	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];


ll Query(int S, int X[], int T, int Y[]) {
	priority_queue<pair<ll, ll> , vector<pair<ll, ll> >, greater<pair<ll, ll> > > pq; allVertex.clear();
	for (int i = 0; i < S; i++) X[i]++, allVertex.push_back(X[i]);
	for (int i = 0; i < T; i++) Y[i]++, allVertex.push_back(Y[i]);
	makeEdge();
	for (auto u : allVertex) dist[u] = 1e18;
	for (int i = 0; i < S; i++) pq.push(mp(0, X[i])), dist[X[i]] = 0;
	for (int 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 (int 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);
	freopen("1test.out", "w", stdout);
#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:40: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:106: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:138:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < b[u].size(); i++) {
                     ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 247456 KB Output is correct
2 Correct 1453 ms 248076 KB Output is correct
3 Correct 1339 ms 247976 KB Output is correct
4 Correct 1306 ms 248296 KB Output is correct
5 Correct 1323 ms 248092 KB Output is correct
6 Correct 986 ms 247944 KB Output is correct
7 Correct 1223 ms 247976 KB Output is correct
8 Correct 1263 ms 247984 KB Output is correct
9 Correct 1219 ms 248092 KB Output is correct
10 Correct 933 ms 247944 KB Output is correct
11 Correct 1223 ms 247976 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 247456 KB Output is correct
2 Correct 2999 ms 280672 KB Output is correct
3 Correct 3316 ms 283776 KB Output is correct
4 Correct 2459 ms 281556 KB Output is correct
5 Correct 2609 ms 303672 KB Output is correct
6 Correct 3433 ms 284100 KB Output is correct
7 Correct 2076 ms 255384 KB Output is correct
8 Correct 1633 ms 254856 KB Output is correct
9 Correct 1506 ms 257840 KB Output is correct
10 Correct 2159 ms 255172 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5249 ms 291504 KB Output is correct
2 Correct 4706 ms 288836 KB Output is correct
3 Correct 5566 ms 293972 KB Output is correct
4 Correct 5183 ms 293704 KB Output is correct
5 Correct 4933 ms 287068 KB Output is correct
6 Correct 4809 ms 304640 KB Output is correct
7 Correct 4286 ms 287484 KB Output is correct
8 Correct 5039 ms 285912 KB Output is correct
9 Correct 4803 ms 285360 KB Output is correct
10 Correct 4576 ms 285744 KB Output is correct
11 Correct 2553 ms 261216 KB Output is correct
12 Correct 2163 ms 259936 KB Output is correct
13 Correct 2406 ms 256148 KB Output is correct
14 Correct 2276 ms 255956 KB Output is correct
15 Correct 2406 ms 256428 KB Output is correct
16 Correct 2383 ms 256312 KB Output is correct