oj.uz

Submission #740363

# Submission time Handle Problem Language Result Execution time Memory
740363 2023-05-12T11:36:40 Z pera Autobus (COCI22_autobus) C++14
0 / 70
 1 ms 724 KB 
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

#define int ll

const ll mod = 1e9 + 7 , N = 71;

int n , m , k , q;
vector<pair<int , int>> G[N];
vector<vector<int>> v(N , vector<int>(N)) , d(N , vector<int>(N)) , id(N , vector<int>(N));
vector<int> f , used(N);

void dfs(int v , int r = 0){
	if(r >= k) return;
	for(auto [to , c] : G[v]){
		if(f[to] == -1 || f[to] > f[v] + c){
			f[to] = f[v] + c;
			dfs(to , r + !used[id[v][to]] ++);
		}
	}
}

main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	for(int i = 1;i < N;i ++){
		for(int j = 1;j < N;j ++) v[i][j] = LLONG_MAX;
	}
	cin >> n >> m;
	for(int i = 1;i <= m;i ++){
		int u , V , t;cin >> u >> V >> t;
		v[u][V] = min(v[u][V] , t);
	}
	int ID = 0;
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= n;j ++){
			if(v[i][j] != LLONG_MAX) id[i][j] = ++ ID , G[i].pb({j , v[i][j]});
		}
	}
	cin >> k >> q;
	for(int i = 1;i <= n;i ++){
		used = vector<int>(N);
		f = vector<int>(N , -1);
		f[i] = 0;
		dfs(i);
		d[i] = f;
	}
	while(q --){
		int c , D;cin >> c >> D;
		cout << d[c][D] << endl;
	}
}

Compilation message

Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:21:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |  for(auto [to , c] : G[v]){
      |           ^
Main.cpp: At global scope:
Main.cpp:29:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   29 | main(){
      | ^~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 724 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -