oj.uz

Submission #541125

# Submission time Handle Problem Language Result Execution time Memory
541125 2022-03-22T10:03:05 Z xuliu Toll (BOI17_toll) C++17
0 / 100
 51 ms 72000 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/K+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);
	for(int i=0; i<=(N/K); 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;
			}
		}
	}
	cin>>k>>n>>m>>o;
	int cntk = n / k + 1; // how many group of size K
	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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 71820 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 71916 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35464 KB Output is correct
2 Correct 15 ms 35540 KB Output is correct
3 Correct 16 ms 35540 KB Output is correct
4 Correct 17 ms 35456 KB Output is correct
5 Correct 15 ms 35496 KB Output is correct
6 Correct 17 ms 35504 KB Output is correct
7 Correct 17 ms 35576 KB Output is correct
8 Correct 16 ms 35540 KB Output is correct
9 Correct 17 ms 35540 KB Output is correct
10 Runtime error 47 ms 72000 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35464 KB Output is correct
2 Correct 15 ms 35540 KB Output is correct
3 Correct 16 ms 35540 KB Output is correct
4 Correct 17 ms 35456 KB Output is correct
5 Correct 15 ms 35496 KB Output is correct
6 Correct 17 ms 35504 KB Output is correct
7 Correct 17 ms 35576 KB Output is correct
8 Correct 16 ms 35540 KB Output is correct
9 Correct 17 ms 35540 KB Output is correct
10 Runtime error 47 ms 72000 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 71820 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -