Submission #1101945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101945		InvMOD	Toll (BOI17_toll)	C++14	7 / 100	47 ms	34928 KiB

toll

#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define int long long

using namespace std;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 5e5+5, Q = 1e6+5;
const int  K = 6, inf = 1e18+1;

struct Query{
    int a,b,id;
    Query(int a = 0, int b = 0, int id = 0): a(a), b(b), id(id) {}
};

int n, m, q, k;
int answer[N], d[6][N];
vector<pair<int,int>> adj[N], r_adj[N];

void Dnc(int l, int r, vector<Query>& Q){
    if(l == r){
        for(Query cur_q : Q){
            answer[cur_q.id] = 0;
        }
        return;
    }
    int m = l+r>>1;

    //cout << "DNC: " << l <<" " << r <<" " << m <<"\n";

    for(int i = l; i <= r; i++){
        for(int j = 0; j < k; j++){
            d[j][i] = inf;
            //cout << d[j][i] <<" ";
        }
        //cout <<"\n";
    }

    for(int i = max(l, m-k*2+1); i <= m; i++){
        for(pair<int,int> e : adj[i]){
            int v = e.fi, w = e.se;
            if(v > m){
                d[(i%k)][i] = 0;
                ckmn(d[(i%k)][v], w);
                //cout << "Avai: " << i <<" " << v <<"\n";
            }
        }
    }

    for(int i = m; i >= l; i--){
        for(pair<int,int> e : r_adj[i]){
            int v = e.fi, w = e.se;
            for(int j = 0; j < k; j++){
                ckmn(d[j][v], d[j][i] + w);
                //cout << "LM: " << d[j][v] <<" " << i <<" " << v <<" " << d[j][i] <<" " << w <<"\n";
            }
        }
    }

    for(int i = m+1; i <= r; i++){
        for(pair<int,int> e : adj[i]){
            int v = e.fi, w = e.se;
            for(int j = 0; j < k; j++){
                ckmn(d[j][v], d[j][i] + w);
            }
        }
    }

    vector<Query> Qleft, Qright;
    for(Query cur_q : Q){
        int l = cur_q.a, r = cur_q.b;
        if(l <= m && r > m){
            int res = inf;
            for(int i = 0; i < k; i++){
                ckmn(res, d[i][l] + d[i][r]);
            }
            ckmn(answer[cur_q.id], res);
        }
        else{
            if(r <= m){
                Qleft.pb(cur_q);
            }
            else Qright.pb(cur_q);
        }
    }

    Dnc(l, m, Qleft);
    Dnc(m+1, r, Qright);
    return;
}

void solve()
{
    cin >> k >> n >> m >> q;

    for(int i = 1; i <= m; i++){
        int a,b,t; cin >> a >> b >> t;
        adj[a].pb(make_pair(b, t));
        r_adj[b].pb(make_pair(a, t));
    }

    vector<Query> Q;
    for(int i = 1; i <= q; i++){
        int a,b; cin >> a >> b;
        Q.pb(Query(a, b, i));
        answer[i] = inf;
    }

    Dnc(0, n, Q);
    for(int i = 1; i <= q; i++){
        cout << (answer[i] == inf ? -1 : answer[i]) <<"\n";
    } cout <<"\n";
}

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

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'void Dnc(long long int, long long int, std::vector<Query>&)':
toll.cpp:32:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int m = l+r>>1;
      |             ~^~
toll.cpp: In function 'int32_t main()':
toll.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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