제출 #1196892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196892		sleepntsheep	물병 (JOI14_bottle)	C11	10 / 100	611 ms	550728 KiB

bottle

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

#define N 2000
#define P 200000
#define M 20000000
#define P_ (P + M)

int n, m, p, q, qwq[N][N], d[N][N], x[P], y[P], qu[N * N], he, ta, dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1}
	, uu[M], vv[M], ww[M], top, ii[M], ff[1 << 16]
	, fa[P_], dfn[P_], dfc, hld[P_], lv[P_], sz[P_], ds[P_], ch[P_][2], l, stamp[P_];

char s[N][N + 1];

void ADD(int u, int v, int w) {
    if (top == M)
	__builtin_trap();
    uu[top] = u, vv[top] = v, ww[top] = w;
    ++top;
}

void SORT() {
    for (int i = 0; i < top; ++i)
	++ff[ww[i]];
    for (int i = 1; i < (1 << 16); ++i)
	ff[i] += ff[i - 1];
    for (int i = 0; i < top; ++i)
	ii[--ff[ww[i]]] = i;
}

void Init() {
    scanf("%d%d%d%d", &n, &m, &p, &q);
    for (int i = 0; i < n; ++i)
	scanf("%s", s[i]);

    for (int i = 0; i < p; ++i)
	scanf("%d%d", x + i, y + i), --x[i], --y[i];
}

void MakeGraph() {
    for (int i = 0; i < p; ++i) {
	qwq[x[i]][y[i]] = i + 1;
	qu[he++] = x[i] * m + y[i];
    }

    for (int u, x, y; he ^ ta;) {
	u = qu[ta++];
	x = u / m, y = u % m;

	for (int nx, ny , j = 0; j < 4; ++j) {
	    int nx = x + dx[j], ny = y + dy[j];
	    if (nx < 0 || ny < 0 || nx >= n || ny >= m || s[nx][ny] == '#')
		continue;

	    if (qwq[nx][ny]) {
		ADD(qwq[nx][ny] - 1, qwq[x][y] - 1, d[nx][ny] + d[x][y]);
	    } else {
		qwq[nx][ny] = qwq[x][y];
		d[nx][ny] = d[x][y] + 1;
		qu[he++] = nx * m + ny;
	    }
	}
    }
    SORT();
}

int ds_find(int i) {
    if (ds[i] == i) return i;
    return ds[i] = ds_find(ds[i]);
}

void dfs(int u) {
    dfn[u] = ++dfc;
    if (~ch[u][0]) {
	hld[ch[u][0]] = hld[u];
	lv[ch[u][0]] = lv[u] + 1;
	dfs(ch[u][0]);
    }
    if (~ch[u][1]) {
	hld[ch[u][1]] = ch[u][1];
	lv[ch[u][1]] = lv[u] + 1;
	dfs(ch[u][1]);
    }
}

void MakeKRT() {
    memset(ch, -1, sizeof ch);
    for (int i = 0; i < p; ++i)
	sz[i] = 1;
    for (int i = 0; i < P_; ++i)
	ds[i] = fa[i] = i;
    l = p;

    for (int i, i_ = 0; i_ < top; ++i_) {
	i = ii[i_];
	if (ds_find(uu[i]) == ds_find(vv[i]))
	    continue;
	uu[i] = ds[uu[i]], vv[i] = ds[vv[i]];
	if (sz[uu[i]] < sz[vv[i]])
	    uu[i] ^= vv[i], vv[i] ^= uu[i], uu[i] ^= vv[i];

	ch[l][0] = uu[i], ch[l][1] = vv[i];
	sz[l] = 1 + sz[uu[i]] + sz[vv[i]];

	fa[uu[i]] = fa[vv[i]] = l;
	ds[uu[i]] = ds[vv[i]] = l;
	//printf(" %d and %d fa = %d\n",uu[i],vv[i],l);
	stamp[l] = ww[i];
	fa[l] = l;

	++l;
    }

    for (int i = l - 1; i >= 0; --i) {
	if (! dfn[i]) {
	    hld[i] = i;
	    lv[i] = 0;
	    dfs(i);
	}
    }
}

int lca(int u, int v) {
    if (ds_find(u) != ds_find(v))
	return -1;
    while (hld[u] ^ hld[v]) {
	if (lv[hld[u]] < lv[hld[v]]) u ^= v, v ^= u, u ^= v;
	u = fa[hld[u]];
    }
    return dfn[u] < dfn[v] ? u : v;
}

void Answer() {
    for (int x, s, t, i = 0; i < q; ++i) {
	scanf("%d%d", &s, &t);
	--s, --t;
	x = lca(s, t);
	if (! ~x)
	    puts("-1");
	else
	    printf("%d\n", stamp[x]);
    }
}

int main() {
    Init(), MakeGraph(), MakeKRT(), Answer();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bottle.c: In function 'Init':
bottle.c:32:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf("%d%d%d%d", &n, &m, &p, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.c:34:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         scanf("%s", s[i]);
      |         ^~~~~~~~~~~~~~~~~
bottle.c:37:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d%d", x + i, y + i), --x[i], --y[i];
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.c: In function 'Answer':
bottle.c:135:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         scanf("%d%d", &s, &t);
      |         ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30