oj.uz

Submission #937016

# Submission time Handle Problem Language Result Execution time Memory
937016 2024-03-03T08:29:14 Z ByeWorld Travelling Merchant (APIO17_merchant) C++14
12 / 100
 41 ms 1876 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define int long long
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<string, pii> ipii;
const int INF = 1e18+10;
const int MAXN = 110;
const int MAXK = 1010;
const int LOG = 20;

int n, m, k;
int b[MAXN][MAXK], s[MAXN][MAXK];
vector <pii> adj[MAXN][3];
int dis[MAXN][3];
priority_queue <pii> pq;

void dji(int nw, int ty){
	for(int i=1; i<=n; i++) dis[i][ty] = INF;
	pq.push({0, nw});
	dis[nw][ty] = 0;

	while(!pq.empty()){
		int nw = pq.top().se; int dist = pq.top().fi; pq.pop();
		if(dist > dis[nw][ty]) continue;

		for(auto ed : adj[nw][ty]){
			int wei = ed.se, nx = ed.fi;
			if(dis[nx][ty] <= dis[nw][ty] + wei) continue;
			dis[nx][ty] = dis[nw][ty] + wei;
			pq.push({dis[nx][ty], nx});
		}
	}
}
signed main(){
	cin >> n >> m >> k;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=k; j++){
			cin >> b[i][j] >> s[i][j];
		}
	}
	for(int i=1; i<=m; i++){
		int x, y, z; cin >> x >> y >> z;
		adj[x][0].pb({y, z});
		adj[y][1].pb({x, z});
	}
	dji(1, 0);
	dji(1, 1);
	int ans = 0;
	//cout << norm << " p\n";

	for(int i=2; i<=n; i++){
		int val = 0;
		for(int j=1; j<=k; j++){
			if(s[i][j] == -1 || b[1][j] == -1) continue;
			int te = s[i][j] - b[1][j];
			val = max(val, te);
		}
		int dist = dis[i][0] + dis[i][1];
		ans = max(ans, val / dist );
		//cout << i << ' ' << dist << ' ' << val << " dist\n";
	}
	cout << ans << '\n';
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1876 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 2 ms 856 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Incorrect 1 ms 860 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

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

Subtask #4
0 / 34.0

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