oj.uz

Submission #381689

# Submission time Handle Problem Language Result Execution time Memory
381689 2021-03-25T16:44:06 Z peijar Toll (BOI17_toll) C++17
0 / 100
 130 ms 157036 KB 
#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 < nbSommets; ++iSommet)
			if (iSommet + (1 << p) < MAXN)
				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;
		for (int p(0); p < MAXP; ++p)
			if ((1<<p) & diff)
			{
				int curPos = from/mod;
				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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 157036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 156908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 156908 KB Output is correct
2 Incorrect 72 ms 156908 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 156908 KB Output is correct
2 Incorrect 72 ms 156908 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 157036 KB Output isn't correct
2 Halted 0 ms 0 KB -