Submission #1262205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262205		nmduck6	Toll (BOI17_toll)	C++20	100 / 100	225 ms	10052 KiB

toll

#include <iostream>
#include <iomanip>
#include <cstdint>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>

// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

#define _F ""
// #define MULTITEST

using namespace std;

#define MAXN 50000
#define MAXQ 10000
#define MAXVAL 1000000000
#define MAXK 5

struct adj_t {
	int v, w;
};

struct query_t {
	int u, v, ind;
};

// edge (u, v) -> b / k = 1 + a / k

int k, n, m, q;
vector<adj_t> adj[MAXN], radj[MAXN];
vector<query_t> queries;
int res[MAXQ];

void pre() {
	cin >> k >> n >> m >> q;
	int u, v, w;
	while (m--) {
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		radj[v].push_back({u, w});
	}
	queries.reserve(q);
	query_t query;
	for (int i = 0; i < q; i++) {
		cin >> query.u >> query.v;
		query.ind = i;
		if (query.v / k <= query.u / k) res[query.ind] = -1;
		else queries.emplace_back(query);
	}
}

int f1[MAXK][MAXN], f2[MAXK][MAXN];

void dijkstra(int s, int blk, int brk, int* dist, vector<adj_t> adj[MAXN]) {
	// k >= blk && k <= brk
	for (int u = blk * k; u <= min(n - 1, (brk + 1) * k - 1); u++) dist[u] = MAXVAL;
	dist[s] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	pq.push({0, s});
	while (!pq.empty()) {
		auto [distu, u] = pq.top(); pq.pop();
		if (distu != dist[u]) continue;
		for (auto [v, w]: adj[u]) {
			if (v / k < blk || v / k > brk) continue;
			if (distu + w < dist[v]) {
				dist[v] = distu + w;
				pq.push({dist[v], v});
			}
		}
	}
}

void dnc(int l, int r, vector<query_t>& queries) {
	if (l > r) return;
	int mid = (l + r) >> 1;
	for (int i = 0; i < k; i++) {
		int u = mid * k + i;
		if (u >= n) break;
		dijkstra(u, l, r, f1[i], radj);
		dijkstra(u, l, r, f2[i], adj);
	}
	vector<query_t> left, right;
	for (query_t& query: queries) {
		if (query.v / k < mid) left.push_back(query);
		else if (query.u / k > mid) right.push_back(query);
		else {
			int resu = MAXVAL;
			for (int i = 0; i < k; i++)
				resu = min(resu, f1[i][query.u] + f2[i][query.v]);
			res[query.ind] = resu == MAXVAL ? -1 : resu;
		}
	}
	dnc(l, mid - 1, left);
	dnc(mid + 1, r, right);
}

void run() {
	dnc(0, (n - 1) / k, queries);
	for (int i = 0; i < q; i++) cout << res[i] << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	if (fopen(_F".inp", "r")) {
		freopen(_F".inp", "r", stdin);
		freopen(_F".out", "w", stdout);
	}
	pre();
	int t = 1;
	#ifdef MULTITEST
	cin >> t;
	#endif
	while (t--) {
		run();
	}
}

/*
                                      #++*                                                          
                                  *-----::--+%                                                      
                                *---::---::--=------------=+##       %%%#                           
                               +-:::::-===-------::::::::::::::=*+-:--::::-+%                       
                             +-::::-=:::::::::::::::::::::--=-::::==:::::::::-*                     
               *#           #=::---::::::::::::::::::::::::::::--:::------:::::=*                   
             ##**          #=:--:::::::::::::::::::::::::::::::::--::::=-::-::::+                   
             #             +:--:::::::::::-::::::::::::::::::::::::--:::--:::-:::*                  
               *          *-+:::::::::::-:::::::::::::::--:::::::::::-:::--:::::::*                 
             **          #==::::::::::--::::::::::::::::::-:::::::::::-::--=:::-::=                 
              *  *       *+::::::::::-:::::::::::::::::::::-:::::::::::--::-=:::-:-+                
            **#          *-:::::::::-:::::::::::::::::::::-:::::::::::::--:::=:::-:-#               
                        *=:::::::::-::::::::::::::::::::::::-::::::::::::-::---:::--*               
                ***     +:::::::::-:::::::::::==:::::::::::::=::::::::::::-:--=::::-+               
                 *     *-::::::::--::::::::::-::--::::::::::::-:::::::::::---:--:::-=               
                       +:::::::::=:::::-:::-::::::-:-::::::::-=::::::::::::--:-=-:::=               
                      *-::::::::--:::-:::--::::::::=:-::::::::=-:::::::::::=-:-=-:::=               
                      +:::::::::=::-:::--::::::::::::=-:::::::-=::::::::::::=:==--::=               
         *====+**    #=:::::::::=-:--=--::-:::::::::::---::::::-::::::::::::=-==--::=               
         *-:::::::--:--:-::::::===-:-::::-::::::::::-:::-==-:::--:::::::::::+-==--::=               
          =-:----------:-::::::-::::::::::::::::::::::--:--:-===-:-:::::::::+==----:=               
            =-:----::--:-::::::-:::::::::::::::::::::::::::::::--:-:::::::::+:::::-==++*##          
              *-:--::----::::::-:::::::::::::::::::::::::::::::--:-:::::::::=--------:::::::-*      
                +-------=::::::-::=####*=::::::::::::::::::::::-::::::::::::-:----------::-=*       
                   +==--*::::::=:::::::::::::::::::::=###*+-:::=:-:::::::-:=---------::--=          
                      +-*=:::::-::::::::::::::::::::::::::=*-::-::::::::-+:=---:--::=+              
                      *:*+-:::::=:::::::::::::::::::::::::::::=:::::::::+-==-::-=+=-=               
                       *=++-::---=:::::::::::::::::::::::::::=:--:::::-+=-=-=+=====-=+              
                       ++*=*=::-===:::::::::::::::::::::::::---=-::::=++=+======------+             
                       =+=+*-=+=-==:::::::::::::::::::::::-==*=-:::-+++=--------=+==+++*            
                      #-*=*+----==++::::::::::-=:::::::::::-==-::=+*=------------=-----=+           
                      *+==*=--------=+=-:::::--======++++--=====----=------------==----=+           
                      +=-------------===+=--------------==-----------=------------=-----=*          
                     *=------------==--------------------=-----------=====--------=-----=+          
                    *=-------------==---------------------=----------=+====-------==+**++*          
                    *=-------------==----------------------=---------=====--------==---==+          
                    *=-------------==--------------------=++----------==----------=======+          
                    #+=------------==------------------=+==-----------=----------==-=====+          
                    +====-----------=----------------=+=====----------=---------=========*          
                    +--:+*+---------+----------------*====-==---------+==------==+=+*+==*           
                   *:-::++=-+==-----=+---------------===---==-----==+*#**=-=+==+++===+              
                   +:-::++-::::-=====+=--------------------==-==++++++++::--::::-+++=+              
                  #::-::++-::::::::::+#------------------=++++=--::-++=::-:::::::-+-=#              
                  *::-::++-::::::::-++*+---------------=++--::::::=++=::-:::::::::-+-*              
                 #-::-::++-:::::::-+++:-=------------=++--:::::::=++=::=:::::::::::==+              
                 *:::--:++=::::::=++-::=+=---------=++--::::::::-+++::-::::::::::::==+              
                 +:::-::=+=::::-+++-::---==-----=++**-:::::::::-+++::-:::::::::::::-==#             
                 =::::-:-++-::-+++::--::::::----*:-++=:::::::::+++::--::::::::::::::=-*             
                #-::::=::++-:-++=::-:::::::::::::::=++-:::::::+++-::-:::::::::::::::+-+             
                *-::::-::=+==++-::-::::::::::::::-::++=::::::=++=::=::::::::::::::::==-*            
                *-:::::-:-++++=::-::::::::::::::::-::++=::::-++=::=:::::::::::::::::-=-+            
                   ::::::-+++=:::::::::::::::::::::::=++-:::=++-:::::::::::::::::::::--             
*/

Compilation message (stderr)

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

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