Submission #381693

#	Time	Username	Problem	Language	Result	Execution time	Memory
381693		peijar	Toll (BOI17_toll)	C++17	100 / 100	168 ms	157164 KiB

toll

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 5e4;
const int MAXP = 16;
const int INF = 2e18;
int mod, nbSommets, nbAretes, nbRequetes;

int dis[MAXP][MAXN][5][5];

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> mod >> nbSommets >> nbAretes >> nbRequetes;
	for (int p(0); p < MAXP; ++p)
		for (int iSommet(0); iSommet < MAXN; ++iSommet)
			for (int iDep(0); iDep < mod; ++iDep)
				for (int iFin(0); iFin < mod; ++iFin)
					dis[p][iSommet][iDep][iFin] = INF;
	while (nbAretes--)
	{
		int u, v, c;
		cin >> u >> v >> c;
		dis[0][u/mod][u%mod][v%mod] = c;
	}
	for (int p(1); p < MAXP; ++p)
		for (int iSommet(0); iSommet + (1 << (p-1))< (nbSommets+mod-1)/mod; ++iSommet)
				for (int iDep(0); iDep < mod; ++iDep)
					for (int iFin(0); iFin < mod; ++iFin)
						for (int iMilieu(0); iMilieu < mod; ++iMilieu)
							dis[p][iSommet][iDep][iFin] = min(dis[p][iSommet][iDep][iFin],
									dis[p-1][iSommet][iDep][iMilieu] + dis[p-1][iSommet + (1<<(p-1))][iMilieu][iFin]);

	array<int, 5> cur, nxt;
	
	for (int iRequete = 0; iRequete < nbRequetes; ++iRequete) 
	{
		int from, to;
		cin >> from >> to;
		int diff = to/mod - from/mod;
		fill(cur.begin(), cur.end(), INF);
		fill(nxt.begin(), nxt.end(), INF);
		cur[from%mod] = 0;
		int curPos = from/mod;
		for (int p(0); p < MAXP; ++p)
			if ((1<<p) & diff)
			{
				for (int iDep(0); iDep < mod; ++iDep)
					for (int iFin(0); iFin < mod; ++iFin)
						nxt[iFin] = min(nxt[iFin], 
								cur[iDep] + dis[p][curPos][iDep][iFin]);
				curPos += 1 << p;
				cur = move(nxt);
				fill(nxt.begin(), nxt.end(), INF);
			}
		int ret = cur[to%mod];
		if (ret == INF) ret = -1;
		cout << ret << '\n';
	}
}

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