Submission #1196908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196908		sleepntsheep	물병 (JOI14_bottle)	C11	0 / 100	261 ms	111148 KiB

bottle

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

#define N 2005
#define P 200000
#define M 20000000
#define M1 300000
#define P_ (P + M1)

int n, m, p, q, qwq[N][N], d[N][N], qu[N * N], he, ta, dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1}
	, uu[M], vv[M], ww[M], ii[M], jj[M], top, ff[1 << 16]
	, fa[P_], hld[P_], lv[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] & ((1 << 16) - 1)];
    for (int i = 1; i < (1 << 16); ++i)
	ff[i] += ff[i - 1];
    for (int i = 0; i < top; ++i)
	jj[--ff[ww[i] & ((1 << 16) - 1)]] = i;
    memset(ff, 0, sizeof ff);
    for (int i = 0; i < top; ++i)
	++ff[ww[i] >> 16];
    for (int i = 1; i < (1 << 16); ++i)
	ff[i] += ff[i - 1];
    for (int i = 0; i < top; ++i)
	ii[--ff[ww[jj[i]] >> 16]] = jj[i];
}

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

}

void MakeGraph() {
    for (int x, y, i = 0; i < p; ++i) {
	scanf("%d%d", &x, &y);
	qwq[--x][--y] = i + 1;
	qu[he++] = x * m + y;
    }

    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) {
	    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;
	    }
	}
    }
    for (int i = 1; i < p; ++i)
	ADD(i - 1, i, 1000000000);
    SORT();
}

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

void dfs(int u) {
    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(ds, -1, sizeof ds);
    memset(ch, -1, sizeof ch);
    l = p;

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

	if (l == P_)
	    __builtin_trap();

	uu[i] = ds_find(uu[i]), vv[i] = ds_find(vv[i]);
	if (-ds[uu[i]] < -ds[vv[i]])
	    uu[i] ^= vv[i], vv[i] ^= uu[i], uu[i] ^= vv[i];

	ch[l][0] = uu[i];
	ch[l][1] = vv[i];

	ds[l] += ds[uu[i]] + ds[vv[i]];
	fa[uu[i]] = fa[vv[i]] = l;
	ds[uu[i]] = ds[vv[i]] = l;
	stamp[l] = ww[i];

	++l;
    }

    --l;
    fa[l] = hld[l] = l;
    lv[l] = 0;
    dfs(l);
}

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

void Answer() {
    for (int x, s, t, i = 0; i < q; ++i) {
	scanf("%d%d", &s, &t);
	x = lca(--s, --t);
	printf("%d\n", stamp[x] >= 1e9 ? -1 : stamp[x]);
    }
}

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

Compilation message (stderr)

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

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