oj.uz

Submission #60389

# Submission time Handle Problem Language Result Execution time Memory
60389 2018-07-24T04:48:35 Z ainta(#1738) Railway Trip (JOI17_railway_trip) C++11
45 / 100
 2000 ms 25148 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#define N_ 101000
using namespace std;
int n, K, Q, w[N_], Num[N_];
vector<int>G[N_], E[N_], L[N_];
set<int>Set;
int BIT[N_][2];
int D1[N_], D2[N_];
void Add(int a, int ck, int b) {
	while (a <= n) {
		BIT[a][ck] += b;
		a += (a&-a);
	}
}
int Sum(int a, int ck) {
	int r = 0;
	while (a) {
		r += BIT[a][ck];
		a -= (a&-a);
	}
	return r;
}

void Add_Edge(int a, int b, int d) {
	E[a].push_back(b);
	L[a].push_back(d);
}

int cnt, v[N_];
struct point {
	int a, dep;
	bool operator<(const point &p)const {
		return dep < p.dep;
	}
};
vector<point>T1, T2;

void DFS(int a) {
	if (cnt & 1) T1.push_back({ a,w[a] });
	else T2.push_back({ a,w[a] });
	v[a] = cnt;
	for (auto &x : E[a]) {
		if (v[x]!=cnt)DFS(x);
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int i;
	scanf("%d%d%d", &n, &K, &Q);
	for (i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
		D1[i] = D2[i] = 1e9;
		G[w[i]].push_back(i);
	}
	for (i = K; i >= 1; i--) {
		if (G[i].empty())continue;
		for (auto &t : G[i]) {
			Add(t, 0, 1);
			Add(t, 1, 1);
		}
		if (!Set.empty()) {
			for (auto &t : G[i]) {
				auto it = Set.lower_bound(t);
				int d1 = 1e9, d2 = 1e9, l, r;
				if (it != Set.end()) {
					d2 = Sum(*it, 0) - Sum(t, 0) + 1;
					r = *it;
				}
				if (it != Set.begin()) {
					it--;
					d1 = Sum(t, 0) - Sum(*it, 0);
					l = *it;
				}
				int M = min(d1, d2);
				if (d1 == M) {
					Add_Edge(t, l, d1);
				}
				if (d2 == M) {
					Add_Edge(t, r, d2);
				}
			}
		}
		for (auto &t : G[i]) {
			Set.insert(t);
			Num[t] = Sum(t, 1);
			Add(t, 0, -1);
		}
	}
	while (Q--) {
		int a, b;
		scanf("%d%d", &a, &b);
		T1.clear();
		T2.clear();
		cnt++;
		DFS(a);
		cnt++;
		DFS(b);
		sort(T1.begin(), T1.end());
		sort(T2.begin(), T2.end());
		D1[a] = 0;
		for (auto &t : T1) {
			int x = t.a;
			for (i = 0; i < E[x].size(); i++) {
				D1[E[x][i]] = min(D1[E[x][i]], D1[x] + L[x][i]);
			}
		}
		D2[b] = 0;
		for (auto &t : T2) {
			int x = t.a;
			for (i = 0; i < E[x].size(); i++) {
				D2[E[x][i]] = min(D2[E[x][i]], D2[x] + L[x][i]);
			}
		}
		int res = 1e9;
		int pv = 0;
		for (i = 0; i < T1.size(); i++) {
			while (pv < T2.size() && T2[pv].dep < T1[i].dep)pv++;
			for (int ii = i; ii < T1.size() && T1[ii].dep == T1[i].dep; ii++) {
				for (int jj = pv; jj < T2.size() && T2[jj].dep == T1[i].dep; jj++) {
					res = min(res, D1[T1[ii].a] + D2[T2[jj].a] + abs(Num[T1[ii].a] - Num[T2[jj].a]));
				}
			}
		}
		for (auto &x : T1)D1[x.a] = 1e9;
		for (auto &x : T2)D2[x.a] = 1e9;
		printf("%d\n", res-1);
	}
}

Compilation message

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &K, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &w[i]);
   ~~~~~^~~~~~~~~~~~~
railway_trip.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7544 KB Output is correct
2 Correct 9 ms 7544 KB Output is correct
3 Correct 11 ms 7712 KB Output is correct
4 Correct 9 ms 7712 KB Output is correct
5 Correct 10 ms 7716 KB Output is correct
6 Correct 11 ms 7716 KB Output is correct
7 Correct 11 ms 7716 KB Output is correct
8 Correct 10 ms 7716 KB Output is correct
9 Correct 8 ms 7716 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7844 KB Output is correct
2 Correct 156 ms 21052 KB Output is correct
3 Correct 135 ms 21452 KB Output is correct
4 Correct 277 ms 21480 KB Output is correct
5 Correct 303 ms 21624 KB Output is correct
6 Correct 310 ms 21956 KB Output is correct
7 Correct 312 ms 23356 KB Output is correct
8 Correct 86 ms 23356 KB Output is correct
9 Correct 564 ms 24932 KB Output is correct
10 Correct 510 ms 24932 KB Output is correct
11 Correct 418 ms 24932 KB Output is correct
12 Correct 335 ms 24932 KB Output is correct
13 Correct 430 ms 24932 KB Output is correct
14 Correct 384 ms 24932 KB Output is correct
15 Correct 431 ms 24932 KB Output is correct
16 Correct 398 ms 24932 KB Output is correct
17 Correct 128 ms 24932 KB Output is correct
18 Correct 196 ms 24932 KB Output is correct
19 Correct 153 ms 24932 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 24932 KB Output is correct
2 Correct 500 ms 24932 KB Output is correct
3 Correct 475 ms 24932 KB Output is correct
4 Correct 477 ms 24932 KB Output is correct
5 Correct 520 ms 24932 KB Output is correct
6 Correct 603 ms 24932 KB Output is correct
7 Correct 641 ms 24932 KB Output is correct
8 Correct 263 ms 24932 KB Output is correct
9 Correct 239 ms 24932 KB Output is correct
10 Correct 437 ms 24932 KB Output is correct
11 Correct 441 ms 24932 KB Output is correct
12 Correct 404 ms 24932 KB Output is correct
13 Correct 441 ms 24932 KB Output is correct
14 Correct 384 ms 24932 KB Output is correct
15 Correct 600 ms 24932 KB Output is correct
16 Correct 867 ms 24932 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1263 ms 24932 KB Output is correct
2 Correct 1331 ms 24932 KB Output is correct
3 Correct 1232 ms 24932 KB Output is correct
4 Correct 1256 ms 24932 KB Output is correct
5 Correct 286 ms 24932 KB Output is correct
6 Execution timed out 2031 ms 25148 KB Time limit exceeded
7 Halted 0 ms 0 KB -