oj.uz

답안 #60387

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
60387 2018-07-24T04:41:30 Z ainta(#1738) Railway Trip (JOI17_railway_trip) C++11
30 / 100
 2000 ms 26012 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;
		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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -