Submission #60387

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
60387	2018-07-24T04:41:30 Z	ainta(#1738)	Railway Trip (JOI17_railway_trip)	C++11	30 / 100	2000 ms	26012 KB

railway_trip

#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;
		for (auto &x : T1)for (auto &y : T2) {
			if (w[x.a] == w[y.a]) {
				res = min(res, D1[x.a] + D2[y.a] + abs(Num[x.a] - Num[y.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	9 ms	7544 KB	Output is correct
2	Correct	16 ms	7664 KB	Output is correct
3	Correct	10 ms	7664 KB	Output is correct
4	Correct	10 ms	7664 KB	Output is correct
5	Correct	9 ms	7664 KB	Output is correct
6	Correct	11 ms	7664 KB	Output is correct
7	Correct	10 ms	7720 KB	Output is correct
8	Correct	11 ms	7720 KB	Output is correct
9	Correct	9 ms	7756 KB	Output is correct

Subtask #2

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	7812 KB	Output is correct
2	Correct	110 ms	21328 KB	Output is correct
3	Correct	151 ms	21980 KB	Output is correct
4	Correct	226 ms	22360 KB	Output is correct
5	Correct	346 ms	22964 KB	Output is correct
6	Correct	274 ms	22964 KB	Output is correct
7	Correct	362 ms	24632 KB	Output is correct
8	Correct	78 ms	24632 KB	Output is correct
9	Execution timed out	2078 ms	26012 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	463 ms	26012 KB	Output is correct
2	Correct	402 ms	26012 KB	Output is correct
3	Correct	512 ms	26012 KB	Output is correct
4	Correct	571 ms	26012 KB	Output is correct
5	Correct	466 ms	26012 KB	Output is correct
6	Correct	528 ms	26012 KB	Output is correct
7	Correct	502 ms	26012 KB	Output is correct
8	Correct	198 ms	26012 KB	Output is correct
9	Correct	265 ms	26012 KB	Output is correct
10	Correct	446 ms	26012 KB	Output is correct
11	Correct	583 ms	26012 KB	Output is correct
12	Correct	491 ms	26012 KB	Output is correct
13	Correct	535 ms	26012 KB	Output is correct
14	Correct	549 ms	26012 KB	Output is correct
15	Correct	626 ms	26012 KB	Output is correct
16	Correct	1000 ms	26012 KB	Output is correct

Subtask #4

0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1312 ms	26012 KB	Output is correct
2	Correct	1252 ms	26012 KB	Output is correct
3	Correct	1146 ms	26012 KB	Output is correct
4	Correct	1144 ms	26012 KB	Output is correct
5	Correct	241 ms	26012 KB	Output is correct
6	Execution timed out	2048 ms	26012 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-