Submission #1093564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093564		Tozzyyyy	Toll (BOI17_toll)	C++14	0 / 100	119 ms	74848 KiB

toll

#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2")
#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<long long, long long>
#define fi first 
#define se second 
#define bit(i,j) ((j >> i) & 1) 
#define lowbit(x) (x & (-x))
#define sigma main
using namespace std;

const long long inf = 1e9+1; 
const int mod = 998244353; 
const int MAXN = 5e4+100;

struct Matrix{
	vector<vector<int>> d;
	void init(int n , int m , int v){
		d.resize(n , vector<int>(m , v));
	}
};
Matrix operator* (const Matrix &a , const Matrix &b){
	Matrix c;
	c.init(a.d.size() , b.d[0].size() , inf);
	for(int i = 0 ; i < a.d.size() ; i++){
		for(int k = 0 ; k < a.d[0].size() ; k++){
			for(int j = 0 ; j < b.d[0].size() ; j++){
				c.d[i][j] = min(c.d[i][j] , a.d[i][k] + b.d[k][j]);
			}
		}
	}
	return c;
}
Matrix M[MAXN];
Matrix Sum[MAXN][17];
int up[MAXN][17];
int32_t sigma(){
  	//freopen("COLOREDBALLS.inp", "r", stdin);
	//freopen("COLOREDBALLS.out", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);

	int k , n , m , o; cin >> k >> n >> m >> o;

	int sum = n / k;
	
	for(int i = 0 ; i <= sum + 1 ; i++) M[i].init(k , k , inf);
	for(int i = 1 ; i <= m ; i++){
		int a , b , t; cin >> a >> b >> t;
		M[a/k].d[a%k][b%k] = t;
	}

	for(int i = 0 ; i < k ; i++) M[sum + 1].d[i][i] = 0;

	for(int i = 0 ; i <= sum ; i++) up[i][0] = i + 1 , Sum[i][0] = M[i];
	up[sum + 1][0] = sum + 1;
	cout << "pass" << endl;
	for(int j = 1 ; j < 17 ; j++){
		for(int i = 0 ; i + (1 << j) - 1 <= sum ; i++){
			up[i][j] = up[up[i][j-1]][j-1];
			Sum[i][j] = Sum[i][j-1] * Sum[up[i][j-1]][j-1];
		}
	}
	while(o--){
		int a , b; cin >> a >> b;
		int s = a/k , t = b/k;
		if(a > b){
			cout << -1 << "\n"; continue;
		}

		Matrix T; 
		T.init(1 , k , inf);
		T.d[0][a % k] = 0;
		int D = t - s , pos = s;
		for(int j = 16 ; j >= 0 ; j--){
			if(bit(j , D)) T = T * Sum[pos][j] , pos = up[pos][j];
		}
		cout << (T.d[0][b % k] >= inf ? -1 : T.d[0][b % k]) << "\n";
	}

	return 0;
}

Compilation message (stderr)

toll.cpp: In function 'Matrix operator*(const Matrix&, const Matrix&)':
toll.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i = 0 ; i < a.d.size() ; i++){
      |                  ~~^~~~~~~~~~~~
toll.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for(int k = 0 ; k < a.d[0].size() ; k++){
      |                   ~~^~~~~~~~~~~~~~~
toll.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    for(int j = 0 ; j < b.d[0].size() ; j++){
      |                    ~~^~~~~~~~~~~~~~~

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