Submission #1005874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005874		sleepntsheep	Construction Project 2 (JOI24_ho_t2)	C11	100 / 100	195 ms	16728 KiB

Main

#include <stdio.h>

#define NN 200000
#define MM 200000

int n, m, l, src, dst, nxt[MM*2+1], hed[NN], cst[MM*2+1], to[MM*2+1];
long long k, dp[NN], dsrc[NN], ddst[NN], answer;
const long long oo = 1e18;

void lnk(int u, int v, int w) {
    static int ii = 1, i;
    i = ii++;
    cst[i] = w;
    to[i] = v;
    nxt[i] = hed[u];
    hed[u] = i;
}

int tt[NN<<1];
int (*min)(int, int);

int mindijk(int i, int j) {
    return dp[i] < dp[j] ? i : j;
}

int minddst(int i, int j) {
    return ddst[i] < ddst[j] ? i : j;
}

void pul(int i) {
    tt[i] = min(tt[i << 1], tt[i << 1 | 1]);
}

void fix(int i) {
    for (i += n; i >>= 1;)
        pul(i);
}

void dijkstra(int src, long long *out) {
    int i;
    for (i = 0; i < n; ++i)
        dp[i] = oo, tt[i + n] = i;
    dp[src] = 0;
    for (i = n; --i;)
        pul(i);

    for (i = 0; i < n; ++i) {
        int u, j;
        u = tt[1];
        out[u] = dp[u];
        dp[u] = oo + 1;
        fix(u);

        for (j = hed[u]; j; j = nxt[j]) {
            int v, w;
            v = to[j], w = cst[j];
            if (dp[v] == oo + 1)
                continue;
            if (dp[v] > out[u] + w)
                dp[v] = out[u] + w, fix(v);
        }
    }
}

int main() {
    int i, a, b, c;

    scanf("%d%d%d%d%d%lld", &n, &m, &src, &dst, &l, &k);
    --src, --dst;
    for (i = 0; i < m; ++i)
        scanf("%d%d%d", &a, &b, &c), lnk(--a, --b, c), lnk(b, a, c);

    min = mindijk;
    dijkstra(src, dsrc);

    if (dsrc[dst] <= k) {
        printf("%lld", n * (n - 1ll) / 2);
        return 0;
    }

    dijkstra(dst, ddst);

    min = minddst;
    for (i = 0; i < n; ++i)
        tt[i + n] = i;
    for (i = n; --i;)
        pul(i);

    for (i = 0; i < n; ++i) {
        dp[i] = ddst[tt[1]];
        ddst[tt[1]] = oo + 1;
        fix(tt[1]);
    }

    for (i = 0; i < n; ++i) {
        int lower, upper, mid;
        lower = -1;
        upper = n;
        while (upper - lower > 1) {
            mid = lower + (upper - lower) / 2;
            if (l + dp[mid] + dsrc[i] <= k)
                lower = mid;
            else
                upper = mid;
        }
        answer += lower + 1;
    }
    printf("%lld", answer);
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:68:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf("%d%d%d%d%d%lld", &n, &m, &src, &dst, &l, &k);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:71:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d%d%d", &a, &b, &c), lnk(--a, --b, c), lnk(b, a, c);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 29 / 29
• Subtask 4: 47 / 47