Submission #388155

#	Time	Username	Problem	Language	Result	Execution time	Memory
388155		erfanmir	Toll (BOI17_toll)	C++17	7 / 100	203 ms	10048 KiB

toll

// In the name of god

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

template < class T > using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >;
  
typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define lc(x)                       (x) << 1
#define rc(x)                       (x) << 1 | 1
#define F                           first
#define S                           second
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define mp                          make_pair
ll poww(ll a, ll b, ll md) {
    ll ans = 1;
    for(; b; b >>= 1, a = a * a % md){
        if(b & 1){
            ans = ans * a % md;
        }
    }
    return ans % md;
}

const int MAXN = 5e4 + 10;
const int MAXK = 5;
const int SQ = 100;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ll INF = 1e18;
int n, m, k, q, b;
ll dp[2][MAXN][MAXK], ans[MAXN];
vector<pii> adj[MAXN], que[MAXN];

ll solve(int v, int u){
    if(v > u){
        return INF;
    }
    int vk, vq, uk, uq;
    ll tmp[MAXK], kmp[MAXK];
    for(int i = 0; i < MAXK; i++){
        tmp[i] = kmp[i] = INF;
    }
    vk = v / k;
    vq = vk / SQ;
    uk = u / k;
    uq = uk / SQ;
    if(vq == uq){
        return dp[b][v][u % k];
    }
    if(vq < uq){
        for(int i = 0; i < k; i++){
            tmp[i] = dp[0][v][i];
        }
        vq++;
    }
    while(vq < uq){
        v = vq * SQ * k;
        for(int i = 0; i < k; i++){
            kmp[i] = tmp[i];
            tmp[i] = INF;
            for(int j = 0; j < k; j++){
                int x = v + j;
                for(auto y : adj[x]){
                    tmp[i] = min(tmp[i], kmp[y.F % k] + y.S + dp[0][x][i]);
                }
            }
        }
        vq++;
    }
    if(vq == uq){
        v = vq * SQ * k;
        for(int i = 0; i < k; i++){
            kmp[i] = tmp[i];
            tmp[i] = INF;
             for(int j = 0; j < k; j++){
                int x = v + j;
                 for(auto y : adj[x]){
                     tmp[i] = min(tmp[i], kmp[y.F % k] + y.S + dp[b][x][i]);
                }
            }
         }
    }
    return tmp[u % k];
}

int main()
{
    scanf("%d %d %d %d", &k, &n, &m, &q);
    for(int i = 0; i < m; i++){
        int v, u, w;
        scanf("%d %d %d", &v, &u, &w);
        adj[u].push_back(mp(v, w));
    }
    for(int i = 0; i < q; i++){
        int v, u;
        scanf("%d %d", &v, &u);
        que[u].push_back(mp(v, i));
    }
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < MAXN; j++){
            for(int l = 0; l < MAXK; l++){
                dp[i][j][l] = INF;
            }
        }
    }
    for(int i = 0; i < n; i++){
        int md = i % k;
        int sk = i / k;
        int sq = sk / SQ;
        if(md == 0){
            b ^= 1;
        }
        dp[b][i][md] = 0;
        for(int  j = sq * SQ * k; j < i - md; j++){
            dp[b][j][md] = INF;
            for(auto u : adj[i]){
                dp[b][j][md] = min(dp[b][j][md], dp[b ^ 1][j][u.F % k] + u.S);
            }
        }
        for(auto u : que[i]){
            ans[u.S] = solve(u.F, i);
            if(ans[u.S] == INF){
                ans[u.S] = -1;
            }
        }
    }
    for(int i = 0; i < q; i++){
        printf("%lld\n", ans[i]);
    }
}

Compilation message (stderr)

toll.cpp:3: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
toll.cpp: In function 'int main()':
toll.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |     scanf("%d %d %d %d", &k, &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |         scanf("%d %d %d", &v, &u, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |         scanf("%d %d", &v, &u);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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