Submission #1278356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278356		hoa208	Toll (BOI17_toll)	C++20	100 / 100	291 ms	6988 KiB

toll

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
const   ll mod = 1e9 + 7;
const   ll INF = 1e18;
//--------------------------------------------------------------------

const ll BLOCK = 250;
const ll N = 50003;
ll n, k, m ,o;
vector<pa> g[N];
ll dp[N * 10];
ll dist[BLOCK + 5][6][6];
void calc(ll block, ll x, ll y, ll stt) {
    if(x > n) return;
    fill(dp + x, dp + y + 1, INF);
    dp[x] = 0;
    ll id = 0;
    FOR(u, x, y) {
        if(dp[u] != INF)
            for(auto e : g[u]) {
                ll v = e.fi, w = e.se;
                dp[v] = min(dp[v], dp[u] + w);
            }
        if(u >= y - k + 1) {
            id++;
            dist[block][stt][id] = dp[u];
        }
    }
    assert(id == k);
}
ll calc2(ll u, ll v) { // tinh luon ans tu u den v vi u v cung block
    fill(dp + u, dp + v + 1, INF);
    dp[u] = 0;
    FOR(i, u, v) {
        if(dp[i] != INF) {
            for(auto e : g[i]) {
                ll j = e.fi, w = e.se;
                dp[j] = min(dp[j], dp[i] + w);
            }
        }
    }
    if(dp[v] < INF) return dp[v];
    return -1;
}
ll c[6], c_new[6];
ll cnt[N], d[N];
void calc3(ll x, ll block) { // day u ve k con cuoi cung trong blockl
    ll y = (block + 1) * BLOCK * k - 1;
    if(y - x + 1 <= k) {
        FOR(i, 1, 5) c[i] = INF;
        c[d[x]] = 0;
        return;
    }
    fill(dp + x, dp + y + 1, INF);
    dp[x] = 0;
    ll id = 0;
    FOR(u, x, y) {
        if(dp[u] != INF)
            for(auto e : g[u]) {
                ll v = e.fi, w = e.se;
                dp[v] = min(dp[v], dp[u] + w);
            }
        if(u >= y - k + 1) {
            id++;
            c[id] = dp[u];
        }
    }
}
ll calc4(ll x, ll y) { // day 5 con cuoi cung cua blockr - 1 ve r
    fill(dp + x, dp + y + 1, INF);
    FOR(i, 1, k) {
        dp[x + i - 1] = c[i];
    }
    FOR(i, x, y) {
        if(dp[i] != INF) {
            for(auto e : g[i]) {
                ll j = e.fi, w = e.se;
                dp[j] = min(dp[j], dp[i] + w);
            }
        }
    }
    if(dp[y] < INF) return dp[y];
    return -1;
}
ll solve(ll u, ll v) {
    ll tangu = u / k, tangv = v / k;
    ll blockl = tangu / BLOCK;
    ll blockr = tangv / BLOCK;
    if(blockl == blockr) return calc2(u, v);
    calc3(u, blockl);
    FOR(block, blockl + 1, blockr - 1) {
        ll xpre = block * BLOCK * k - k;
        FOR(i, 1, k) c_new[i] = INF;
        FOR(i, 1, k) {
            for(auto e : g[xpre]) {
                ll y = e.fi, w = e.se;
                c_new[d[y]] = min(c_new[d[y]], c[i] + w);
            }
            xpre++;
        }
        FOR(j, 1, k) {
            c[j] = INF;
            FOR(i, 1, k) {
                if(dist[block][i][j] > INF) continue;
                c[j] = min(c[j], c_new[i] + dist[block][i][j]);
            }
        }
    }
    return calc4(blockr * BLOCK * k - k, v);
}
void hbmt() {
    cin >> k >> n >> m >> o;
    FOR(i, 0, n - 1) {
        d[i] = ++cnt[i / k];
    }
    FOR(i, 1, m) {
        ll u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }
    memset(dist, 0x3f, sizeof dist);
    for(int i = 0; i * BLOCK * k <= n; i++) {
        ll x = i * BLOCK * k; // so dau tien cua tang 
        ll y = (i + 1) * BLOCK * k - 1; // so cuoi cung cua tang
        FOR(j, 1, k) {
            calc(i, x, y, j);
            x++;
        }
    }
    FOR(i, 1, o) {
        ll u, v ;
        cin >> u >> v;
        ll tangu = u / k, tangv = v / k;
        cout << solve(u, v) << '\n';
    }
}

int main() {
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    #define NAME "hbmt"
    if(fopen(NAME".inp", "r")) {
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    
    //int t;cin>>t;while(t--)
    hbmt();
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:152:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:153:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44