oj.uz

Submission #541126

# Submission time Handle Problem Language Result Execution time Memory
541126 2022-03-22T10:08:38 Z xuliu Toll (BOI17_toll) C++17
100 / 100
 287 ms 177356 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld long double 
#define debug if(0)

typedef array<array<ll, 5>, 5> ar;

const int N = 5e4, M = 17, K = 5;
const ll inf = 1e18 + 4;
int k, n, m, o;
ar dist[N+4][M+1];

pair<int, int> change(int x) {
	// change from x -> Ka + b
	int a = x / k, b = x % k;
	return {a, b};
}

void combine(ar &t, ar a, ar b) {
	for(int x=0; x<5; x++) {
		for(int y=0; y<5; y++) {
			for(int z=0; z<5; z++) {
				t[x][y] = min(t[x][y], a[x][z]+b[z][y]);
			}
		}
	}
}

void print(ar a) {
	cerr<<"===\n";
	for(int i=0; i<5; i++) {
		for(int j=0; j<5; j++) {
			if(a[i][j] == inf) cerr<<"inf";
			else cerr<<a[i][j];
			cerr<<" ";
		}
		cerr<<"\n";
	}
	cerr<<"===\n";
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>k>>n>>m>>o;
	int cntk = n / k + 1; // how many group of size K
	for(int i=0; i<=cntk+1; i++) {
		for(int j=0; j<M; j++) {
			for(int x=0; x<5; x++) {
				for(int y=0; y<5; y++) dist[i][j][x][y] = inf;
			}
		}
	}
	for(int i=0; i<m; i++) {
		int a, b, t, xa, ya, xb, yb; cin>>a>>b>>t;
		tie(xa, ya) = change(a);
		tie(xb, yb) = change(b);
		// xb-xa = 1
		dist[xa][0][ya][yb] = min(dist[xa][0][ya][yb], (ll) t);
	}
	for(int j=1; j<M; j++) {
		for(int i=0; i<=cntk; i++) {
			if(i+(1<<(j-1)) > cntk) break;
			combine(dist[i][j], dist[i][j-1], dist[i+(1<<(j-1))][j-1]);
			/*for(int z=0; z<5; z++) {
				for(int x=0; x<5; x++) {
					for(int y=0; y<5; y++) {
						ll ret = dist[i][j-1][x][z] + dist[i+(1<<(j-1))][j-1][z][y];
						dist[i][j][x][y] = min(dist[i][j][x][y], ret);
					}
				}
			}*/
		}
	}
	debug {
		cerr<<"dist[0][0]: \n";
		print(dist[0][0]);
		cerr<<"\n dist[1][0]: \n";
		print(dist[1][0]);
		cerr<<"\n dist[0][1]: \n";
		print(dist[0][1]);
		cerr<<"\n\n\n\n\n";
	}
	for(int i=0; i<o; i++) {
		int a, b; cin>>a>>b;
		int xa, ya, xb, yb;
		tie(xa, ya) = change(a);
		tie(xb, yb) = change(b);
		int diff = xb - xa;
		if(diff <= 0) { cout<<"-1\n"; continue; }
		int px = xa + 1;
		ar ans = dist[xa][0]; diff--;
		ar base;
		for(int x=0; x<5; x++) {
			for(int y=0; y<5; y++) base[x][y] = inf;
		}
		debug cerr<<"diff to do = "<<diff<<"\n";
		for(int j=0; j<M; j++) {
			if(diff & (1<<j)) {
				debug {
					cerr<<"j = "<<j<<", combine:\nans: \n"; print(ans);
					cerr<<"and dist["<<px<<"][j]: \n";
					print(dist[px][j]);
					cerr<<"result new ans: \n";
					print(ans);
					cerr<<"\n\n\n";
				}
				ar oldans = ans;
				ans = base;
				combine(ans, oldans, dist[px][j]);
				px += (1<<j);
			}
		}
		cout<<(ans[ya][yb] == inf ? -1 : ans[ya][yb])<<"\n";
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 177340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 4 ms 3796 KB Output is correct
6 Correct 4 ms 3796 KB Output is correct
7 Correct 5 ms 3796 KB Output is correct
8 Correct 281 ms 177356 KB Output is correct
9 Correct 287 ms 177324 KB Output is correct
10 Correct 260 ms 176480 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 90024 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 13 ms 3928 KB Output is correct
8 Correct 11 ms 2212 KB Output is correct
9 Correct 272 ms 177320 KB Output is correct
10 Correct 128 ms 61280 KB Output is correct
11 Correct 168 ms 90064 KB Output is correct
12 Correct 112 ms 60244 KB Output is correct
13 Correct 77 ms 23744 KB Output is correct
14 Correct 76 ms 36988 KB Output is correct
15 Correct 58 ms 22604 KB Output is correct
16 Correct 44 ms 22600 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 3876 KB Output is correct
7 Correct 3 ms 2132 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 3 ms 1236 KB Output is correct
10 Correct 247 ms 177244 KB Output is correct
11 Correct 153 ms 89836 KB Output is correct
12 Correct 110 ms 61180 KB Output is correct
13 Correct 120 ms 61388 KB Output is correct
14 Correct 111 ms 60832 KB Output is correct
15 Correct 41 ms 22608 KB Output is correct
16 Correct 41 ms 22604 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 3876 KB Output is correct
7 Correct 3 ms 2132 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 3 ms 1236 KB Output is correct
10 Correct 247 ms 177244 KB Output is correct
11 Correct 153 ms 89836 KB Output is correct
12 Correct 110 ms 61180 KB Output is correct
13 Correct 120 ms 61388 KB Output is correct
14 Correct 111 ms 60832 KB Output is correct
15 Correct 41 ms 22608 KB Output is correct
16 Correct 41 ms 22604 KB Output is correct
17 Correct 143 ms 89932 KB Output is correct
18 Correct 1 ms 328 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 328 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 6 ms 3796 KB Output is correct
24 Correct 4 ms 2132 KB Output is correct
25 Correct 4 ms 1108 KB Output is correct
26 Correct 4 ms 1240 KB Output is correct
27 Correct 246 ms 177280 KB Output is correct
28 Correct 121 ms 61244 KB Output is correct
29 Correct 136 ms 61440 KB Output is correct
30 Correct 114 ms 60860 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 177340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 4 ms 3796 KB Output is correct
6 Correct 4 ms 3796 KB Output is correct
7 Correct 5 ms 3796 KB Output is correct
8 Correct 281 ms 177356 KB Output is correct
9 Correct 287 ms 177324 KB Output is correct
10 Correct 260 ms 176480 KB Output is correct
11 Correct 172 ms 90024 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 13 ms 3928 KB Output is correct
18 Correct 11 ms 2212 KB Output is correct
19 Correct 272 ms 177320 KB Output is correct
20 Correct 128 ms 61280 KB Output is correct
21 Correct 168 ms 90064 KB Output is correct
22 Correct 112 ms 60244 KB Output is correct
23 Correct 77 ms 23744 KB Output is correct
24 Correct 76 ms 36988 KB Output is correct
25 Correct 58 ms 22604 KB Output is correct
26 Correct 44 ms 22600 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 4 ms 3876 KB Output is correct
33 Correct 3 ms 2132 KB Output is correct
34 Correct 2 ms 980 KB Output is correct
35 Correct 3 ms 1236 KB Output is correct
36 Correct 247 ms 177244 KB Output is correct
37 Correct 153 ms 89836 KB Output is correct
38 Correct 110 ms 61180 KB Output is correct
39 Correct 120 ms 61388 KB Output is correct
40 Correct 111 ms 60832 KB Output is correct
41 Correct 41 ms 22608 KB Output is correct
42 Correct 41 ms 22604 KB Output is correct
43 Correct 143 ms 89932 KB Output is correct
44 Correct 1 ms 328 KB Output is correct
45 Correct 1 ms 340 KB Output is correct
46 Correct 1 ms 328 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 1 ms 340 KB Output is correct
49 Correct 6 ms 3796 KB Output is correct
50 Correct 4 ms 2132 KB Output is correct
51 Correct 4 ms 1108 KB Output is correct
52 Correct 4 ms 1240 KB Output is correct
53 Correct 246 ms 177280 KB Output is correct
54 Correct 121 ms 61244 KB Output is correct
55 Correct 136 ms 61440 KB Output is correct
56 Correct 114 ms 60860 KB Output is correct
57 Correct 128 ms 47676 KB Output is correct
58 Correct 270 ms 177356 KB Output is correct
59 Correct 175 ms 90128 KB Output is correct