oj.uz

Submission #696627

# Submission time Handle Problem Language Result Execution time Memory
696627 2023-02-07T01:51:59 Z LeDaiKing Autobus (COCI22_autobus) C++17
30 / 70
 1000 ms 7008 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>

using namespace std;

#define NMOD 3
#define ll long long
#define fi first
#define se second
#define pb push_back
#define log 17
#define mask(i) (1ll << (i))
#define setp(x) setprecision(x)
#define ALL(v) v.begin(), v.end()
#define ck(n, i) (((n) >> (i)) & 1) 
#define getbit(x) __builtin_popcount(x)

const double PI = acos(-1);
const long long MOD = 1e9 + 7;
const long long MOD1 = 998244353;
const long long MODo = 123456789;

const int oo = 1e9;
const long long oo15 = 1e15, oo18 = 1e18+3, oooo = 922372036854775807;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct DATA
{
	int st, tt, len;

	bool operator < (const DATA &o) const
	{
		return len > o.len;
	}
};

int dist[72][72][72];
vector<pair<int,int>> a[72];

void solve() 
{
	int n, m;

	cin >> n >> m;

	for (int i = 1; i <= m; i++)
	{
		int u, v, t;
		cin >> u >> v >> t;
		a[u].pb({v, t});
	}

	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++)
	for (int e = 0; e <= n; e++)
	dist[i][j][e] = oo;

	int k, q;
	cin >> k >> q;
	k = min(k, n);

	for (int st = 1; st <= n; st++)
	{
		priority_queue<DATA> qe;
		dist[st][st][0] = 0;
		qe.push({st, 0, 0});
		// cout << st << endl;
		while(!qe.empty())
		{
			int u = qe.top().st, tt = qe.top().tt, len = qe.top().len; qe.pop();
			// cout << u << " " << tt << " " << len << endl;
			if (dist[st][u][tt] != len || tt == k) continue;

			for (auto v : a[u])
			if (dist[st][v.fi][tt + 1] > len + v.se)
			{
				dist[st][v.fi][tt + 1] = len + v.se;
				if (tt + 1 < k)
				qe.push({v.fi, tt + 1, dist[st][v.fi][tt + 1]});
			}
		}
	}

	while(q--)
	{
		int u, v;
		cin >> u >> v;
		int ans = oo;
		for (int i = 0; i <= k; i++) ans = min(ans, dist[u][v][i]);

		if (ans == oo) cout << "-1\n"; else cout << ans << "\n";
	}

}

int main() 
{   
   
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);  
    int testcase = 1;
    //cin >> testcase;
    while(testcase--)
        solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 2 ms 1748 KB Output is correct
3 Correct 3 ms 1748 KB Output is correct
4 Correct 2 ms 1748 KB Output is correct
5 Correct 3 ms 1748 KB Output is correct
6 Correct 4 ms 1748 KB Output is correct
7 Correct 5 ms 1876 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 24 ms 1808 KB Output is correct
8 Correct 78 ms 1836 KB Output is correct
9 Correct 4 ms 1748 KB Output is correct
10 Correct 52 ms 1812 KB Output is correct
11 Correct 24 ms 1900 KB Output is correct
12 Correct 126 ms 2076 KB Output is correct
13 Correct 208 ms 6528 KB Output is correct
14 Correct 285 ms 6620 KB Output is correct
15 Execution timed out 1084 ms 7008 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 2 ms 1748 KB Output is correct
8 Correct 2 ms 1748 KB Output is correct
9 Correct 3 ms 1748 KB Output is correct
10 Correct 2 ms 1748 KB Output is correct
11 Correct 3 ms 1748 KB Output is correct
12 Correct 4 ms 1748 KB Output is correct
13 Correct 5 ms 1876 KB Output is correct
14 Correct 24 ms 1808 KB Output is correct
15 Correct 78 ms 1836 KB Output is correct
16 Correct 4 ms 1748 KB Output is correct
17 Correct 52 ms 1812 KB Output is correct
18 Correct 24 ms 1900 KB Output is correct
19 Correct 126 ms 2076 KB Output is correct
20 Correct 208 ms 6528 KB Output is correct
21 Correct 285 ms 6620 KB Output is correct
22 Execution timed out 1084 ms 7008 KB Time limit exceeded
23 Halted 0 ms 0 KB -