oj.uz

Submission #940834

# Submission time Handle Problem Language Result Execution time Memory
940834 2024-03-07T17:52:26 Z rainboy 가장 안전한 경로 (TOKI14_safest) C
100 / 100
 18 ms 49756 KB 
#include <stdio.h>
#include <string.h>

#define N	2500
#define N_	500
#define M	(N_ * (N_ - 1) / 2)

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int ej[N][N], ew[N][N], eo[N];

void append(int i, int j, int w) {
	ej[i][eo[i]] = j, ew[i][eo[i]] = w, eo[i]++;
}

char visited[N]; int t, d_, w_;

int dfs(int i, int d) {
	int o;

	if (visited[i])
		return 0;
	visited[i] = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o], w = ew[i][o];

		if (j == t) {
			d_ = d + w, w_ = w;
			return 1;
		}
		if (dfs(j, d + w))
			return 1;
	}
	return 0;
}

int ii[M], jj[M], ww[M];

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (ww[hh[j]] == ww[h])
				j++;
			else if (ww[hh[j]] < ww[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

int ds[N], rr[N];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i, rr[i] = rr[j];
	}
}

int main() {
	static int dd[N], dd_[N], dd1[N], pp[N], hh[M];
	int n, m, s, h, h_, i, i_, j, o, d, w, d1, w1, d2, w2;

	scanf("%d%d%d%d", &n, &m, &s, &t), s--, t--;
	for (h = 0; h < m; h++) {
		scanf("%d%d%d", &i, &j, &w), i--, j--;
		append(i, j, w), append(j, i, w);
	}
	if (n <= N_) {
		memset(dd, 0x3f, n * sizeof *dd), dd[t] = 0;
		memset(pp, -1, n * sizeof *pp);
		memset(visited, 0, n * sizeof *visited);
		while (1) {
			i_ = -1;
			for (i = 0; i < n; i++)
				if (!visited[i] && (i_ == -1 || dd[i_] > dd[i]))
					i_ = i;
			if (i_ == -1)
				break;
			i = i_;
			visited[i] = 1;
			for (o = eo[i]; o--; ) {
				j = ej[i][o], w = ew[i][o], d = dd[i] + w;
				if (!visited[j] && dd[j] > d)
					dd[j] = d, pp[j] = i;
			}
		}
		m = 0;
		for (i = 0; i < n; i++)
			for (o = eo[i]; o--; ) {
				j = ej[i][o], w = ew[i][o];
				if (i < j && pp[i] != j && pp[j] != i)
					ii[m] = i, jj[m] = j, ww[m] = dd[i] + dd[j] + w, m++;
			}
		for (h = 0; h < m; h++)
			hh[h] = h;
		sort(hh, 0, m);
		memset(dd_, 0x3f, n * sizeof *dd_);
		memset(ds, -1, n * sizeof *ds);
		for (i = 0; i < n; i++)
			rr[i] = i;
		for (h = 0; h < m; h++) {
			h_ = hh[h], i = ii[h_], j = jj[h_], w = ww[h_];
			while ((i = rr[find(i)]) != (j = rr[find(j)]))
				if (dd[i] > dd[j])
					dd_[i] = w - dd[i], join(i, pp[i]);
				else
					dd_[j] = w - dd[j], join(j, pp[j]);
		}
		memset(dd1, 0x3f, n * sizeof *dd1), dd1[t] = 0;
		memset(visited, 0, n * sizeof *visited);
		while (1) {
			i_ = -1;
			for (i = 0; i < n; i++)
				if (!visited[i] && (i_ == -1 || dd1[i_] > dd1[i]))
					i_ = i;
			if (i_ == -1)
				break;
			i = i_;
			visited[i] = 1;
			for (o = eo[i]; o--; ) {
				j = ej[i][o], w = ew[i][o], d = max(dd1[i] + w, pp[j] == i ? dd_[j] : dd[j]);
				if (!visited[j])
					dd1[j] = min(dd1[j], d);
			}
		}
		printf("%d\n", dd1[s]);
	} else {
		visited[s] = 0, dfs(s, 0), d1 = d_, w1 = w_;
		visited[s] = 0, dfs(s, 0), d2 = d_, w2 = w_;
		printf("%d\n", min(max(d1, d2 + (d1 - w1) * 2), max(d2, d1 + (d2 - w2) * 2)));
	}
	return 0;
}

Compilation message

safest.c: In function 'main':
safest.c:89:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  scanf("%d%d%d%d", &n, &m, &s, &t), s--, t--;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
safest.c:91:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   scanf("%d%d%d", &i, &j, &w), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 6 ms 8888 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 4 ms 8796 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 16 ms 13916 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 18 ms 14256 KB Output is correct
6 Correct 7 ms 13148 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 49756 KB Output is correct
2 Correct 6 ms 49756 KB Output is correct
3 Correct 7 ms 49756 KB Output is correct
4 Correct 7 ms 49752 KB Output is correct