제출 #541123

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
541123		xuliu	Railway (BOI17_railway)	C++17	0 / 100	29 ms	36428 KiB

railway

#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 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25