oj.uz

답안 #1115807

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1115807 2024-11-21T01:35:43 Z vjudge1 Toll (BOI17_toll) C++17
100 / 100
 166 ms 74116 KB 
#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;
	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

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
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 74116 KB Output is correct
2 Correct 8 ms 22608 KB Output is correct
3 Correct 8 ms 22608 KB Output is correct
4 Correct 8 ms 22764 KB Output is correct
5 Correct 10 ms 23376 KB Output is correct
6 Correct 10 ms 23376 KB Output is correct
7 Correct 10 ms 23376 KB Output is correct
8 Correct 137 ms 73944 KB Output is correct
9 Correct 138 ms 73948 KB Output is correct
10 Correct 126 ms 74056 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 70984 KB Output is correct
2 Correct 8 ms 22608 KB Output is correct
3 Correct 8 ms 22608 KB Output is correct
4 Correct 8 ms 22780 KB Output is correct
5 Correct 8 ms 22608 KB Output is correct
6 Correct 8 ms 22608 KB Output is correct
7 Correct 14 ms 23380 KB Output is correct
8 Correct 14 ms 23376 KB Output is correct
9 Correct 128 ms 74056 KB Output is correct
10 Correct 134 ms 65332 KB Output is correct
11 Correct 117 ms 70928 KB Output is correct
12 Correct 137 ms 65244 KB Output is correct
13 Correct 81 ms 46200 KB Output is correct
14 Correct 82 ms 47800 KB Output is correct
15 Correct 63 ms 46152 KB Output is correct
16 Correct 62 ms 46260 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 22608 KB Output is correct
2 Correct 7 ms 22608 KB Output is correct
3 Correct 7 ms 22620 KB Output is correct
4 Correct 7 ms 22608 KB Output is correct
5 Correct 8 ms 22608 KB Output is correct
6 Correct 9 ms 23376 KB Output is correct
7 Correct 9 ms 23120 KB Output is correct
8 Correct 10 ms 23132 KB Output is correct
9 Correct 9 ms 23136 KB Output is correct
10 Correct 116 ms 74064 KB Output is correct
11 Correct 97 ms 70728 KB Output is correct
12 Correct 122 ms 65096 KB Output is correct
13 Correct 156 ms 65104 KB Output is correct
14 Correct 125 ms 65096 KB Output is correct
15 Correct 73 ms 46116 KB Output is correct
16 Correct 72 ms 46240 KB Output is correct

Subtask #4
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 22608 KB Output is correct
2 Correct 7 ms 22608 KB Output is correct
3 Correct 7 ms 22620 KB Output is correct
4 Correct 7 ms 22608 KB Output is correct
5 Correct 8 ms 22608 KB Output is correct
6 Correct 9 ms 23376 KB Output is correct
7 Correct 9 ms 23120 KB Output is correct
8 Correct 10 ms 23132 KB Output is correct
9 Correct 9 ms 23136 KB Output is correct
10 Correct 116 ms 74064 KB Output is correct
11 Correct 97 ms 70728 KB Output is correct
12 Correct 122 ms 65096 KB Output is correct
13 Correct 156 ms 65104 KB Output is correct
14 Correct 125 ms 65096 KB Output is correct
15 Correct 73 ms 46116 KB Output is correct
16 Correct 72 ms 46240 KB Output is correct
17 Correct 112 ms 70936 KB Output is correct
18 Correct 8 ms 22756 KB Output is correct
19 Correct 8 ms 22608 KB Output is correct
20 Correct 9 ms 22608 KB Output is correct
21 Correct 10 ms 22608 KB Output is correct
22 Correct 9 ms 22752 KB Output is correct
23 Correct 15 ms 23376 KB Output is correct
24 Correct 11 ms 23376 KB Output is correct
25 Correct 12 ms 23060 KB Output is correct
26 Correct 12 ms 23120 KB Output is correct
27 Correct 134 ms 73992 KB Output is correct
28 Correct 166 ms 65040 KB Output is correct
29 Correct 148 ms 65036 KB Output is correct
30 Correct 144 ms 65036 KB Output is correct

Subtask #5
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 74116 KB Output is correct
2 Correct 8 ms 22608 KB Output is correct
3 Correct 8 ms 22608 KB Output is correct
4 Correct 8 ms 22764 KB Output is correct
5 Correct 10 ms 23376 KB Output is correct
6 Correct 10 ms 23376 KB Output is correct
7 Correct 10 ms 23376 KB Output is correct
8 Correct 137 ms 73944 KB Output is correct
9 Correct 138 ms 73948 KB Output is correct
10 Correct 126 ms 74056 KB Output is correct
11 Correct 114 ms 70984 KB Output is correct
12 Correct 8 ms 22608 KB Output is correct
13 Correct 8 ms 22608 KB Output is correct
14 Correct 8 ms 22780 KB Output is correct
15 Correct 8 ms 22608 KB Output is correct
16 Correct 8 ms 22608 KB Output is correct
17 Correct 14 ms 23380 KB Output is correct
18 Correct 14 ms 23376 KB Output is correct
19 Correct 128 ms 74056 KB Output is correct
20 Correct 134 ms 65332 KB Output is correct
21 Correct 117 ms 70928 KB Output is correct
22 Correct 137 ms 65244 KB Output is correct
23 Correct 81 ms 46200 KB Output is correct
24 Correct 82 ms 47800 KB Output is correct
25 Correct 63 ms 46152 KB Output is correct
26 Correct 62 ms 46260 KB Output is correct
27 Correct 8 ms 22608 KB Output is correct
28 Correct 7 ms 22608 KB Output is correct
29 Correct 7 ms 22620 KB Output is correct
30 Correct 7 ms 22608 KB Output is correct
31 Correct 8 ms 22608 KB Output is correct
32 Correct 9 ms 23376 KB Output is correct
33 Correct 9 ms 23120 KB Output is correct
34 Correct 10 ms 23132 KB Output is correct
35 Correct 9 ms 23136 KB Output is correct
36 Correct 116 ms 74064 KB Output is correct
37 Correct 97 ms 70728 KB Output is correct
38 Correct 122 ms 65096 KB Output is correct
39 Correct 156 ms 65104 KB Output is correct
40 Correct 125 ms 65096 KB Output is correct
41 Correct 73 ms 46116 KB Output is correct
42 Correct 72 ms 46240 KB Output is correct
43 Correct 112 ms 70936 KB Output is correct
44 Correct 8 ms 22756 KB Output is correct
45 Correct 8 ms 22608 KB Output is correct
46 Correct 9 ms 22608 KB Output is correct
47 Correct 10 ms 22608 KB Output is correct
48 Correct 9 ms 22752 KB Output is correct
49 Correct 15 ms 23376 KB Output is correct
50 Correct 11 ms 23376 KB Output is correct
51 Correct 12 ms 23060 KB Output is correct
52 Correct 12 ms 23120 KB Output is correct
53 Correct 134 ms 73992 KB Output is correct
54 Correct 166 ms 65040 KB Output is correct
55 Correct 148 ms 65036 KB Output is correct
56 Correct 144 ms 65036 KB Output is correct
57 Correct 166 ms 65096 KB Output is correct
58 Correct 166 ms 73936 KB Output is correct
59 Correct 133 ms 70932 KB Output is correct