Submission #484581

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
484581	2021-11-04T13:22:40 Z	rainboy	Alias (COCI21_alias)	C	70 / 70	13 ms	8268 KB

alias

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	1000
#define M	1000
#define L	20
#define INF	0x3f3f3f3f3f3f3f3fLL

char ss[N][L + 1];
int *ej[N], *ew[N], eo[N], n;

int idx(char *s) {
	int i;

	for (i = 0; i < n; i++)
		if (strcmp(ss[i], s) == 0)
			return i;
	strcpy(ss[n], s);
	ej[n] = (int *) malloc(2 * sizeof *ej[n]);
	ew[n] = (int *) malloc(2 * sizeof *ew[n]);
	return n++;
}

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

	if (o >= 2 && (o & o - 1) == 0) {
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
		ew[i] = (int *) realloc(ew[i], o * 2 * sizeof *ew[i]);
	}
	ej[i][o] = j, ew[i][o] = w;
}

long long *dd_; int pq[N], iq[1 + N], cnt;

int lt(int i, int j) { return dd_[i] < dd_[j]; }

int p2(int p) {
	return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}

void pq_up(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add_last(int i) {
	iq[pq[i] = ++cnt] = i;
}

int pq_remove_first() {
	int i = iq[1], j = iq[cnt--];

	if (j != i)
		pq[j] = 1, pq_dn(j);
	pq[i] = 0;
	return i;
}

void dijkstra(long long *dd, int i) {
	memset(dd, 0x3f, n * sizeof *dd), dd_ = dd;
	dd[i] = 0, pq_add_last(i);
	while (cnt) {
		int o;

		i = pq_remove_first();
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];
			long long d = dd[i] + ew[i][o];

			if (dd[j] > d) {
				if (dd[j] == INF)
					pq_add_last(j);
				dd[j] = d, pq_up(j);
			}
		}
	}
}

int main() {
	static long long dd[N][N];
	int m, q, h, i, j;

	scanf("%d%d", &n, &m);
	n = 0;
	for (h = 0; h < m; h++) {
		static char s[L + 1], t[L + 1];
		int w;

		scanf("%s%s%d", s, t, &w), i = idx(s), j = idx(t);
		append(i, j, w);
	}
	scanf("%d", &q);
	for (i = 0; i < n; i++)
		dijkstra(dd[i], i);
	while (q--) {
		static char s[L + 1], t[L + 1];

		scanf("%s%s", s, t), i = idx(s), j = idx(t);
		if (dd[i][j] == INF)
			printf("Roger\n");
		else
			printf("%lld\n", dd[i][j]);
	}
	return 0;
}

Compilation message

alias.c: In function 'append':
alias.c:28:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   28 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
alias.c: In function 'main':
alias.c:96:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
alias.c:102:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   scanf("%s%s%d", s, t, &w), i = idx(s), j = idx(t);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~
alias.c:105:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
alias.c:111:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   scanf("%s%s", s, t), i = idx(s), j = idx(t);
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	2 ms	588 KB	Output is correct
4	Correct	4 ms	844 KB	Output is correct
5	Correct	12 ms	7316 KB	Output is correct
6	Correct	12 ms	7332 KB	Output is correct
7	Correct	13 ms	8268 KB	Output is correct