oj.uz

Submission #801765

# Submission time Handle Problem Language Result Execution time Memory
801765 2023-08-02T07:31:39 Z SanguineChameleon Travelling Merchant (CCO21_day2problem1) C++17
5 / 25
 970 ms 27908 KB 
#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct edge {
	int v, a, b;

	edge(int _v, int _a, int _b): v(_v), a(_a), b(_b) {};
};

const int maxn = 2e5 + 20;
const int inf = 1e9 + 20;
vector<edge> adj[maxn];
int lt[maxn];
int rt[maxn];
bool flag[maxn];

bool dfs(int u, int x) {
	if (x < lt[u]) {
		return false;
	}
	if (x >= rt[u]) {
		return true;
	}
	flag[u] = true;
	for (auto e: adj[u]) {
		if (x >= e.a) {
			if (flag[e.v] || dfs(e.v, min(inf, x + e.b))) {
				flag[u] = false;
				rt[u] = x;
				return true;
			}
		}
	}
	flag[u] = false;
	lt[u] = x + 1;
	return false;
}

void just_do_it() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, a, b;
		cin >> u >> v >> a >> b;
		adj[u].emplace_back(v, a, b);
	}
	for (int i = 1; i <= n; i++) {
		lt[i] = 0;
		rt[i] = inf + 1;
	}
	for (int i = 1; i <= n; i++) {
		int lt = 1;
		int rt = inf;
		int res = -1;
		while (lt <= rt) {
			int mt = (lt + rt) / 2;
			if (dfs(i, mt)) {
				res = mt;
				rt = mt - 1;
			}
			else {
				lt = mt + 1;
			}
		}
		cout << res << " ";
	}
}

Subtask #1
0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 11860 KB Output is correct
2 Correct 145 ms 11820 KB Output is correct
3 Correct 59 ms 9020 KB Output is correct
4 Correct 42 ms 7536 KB Output is correct
5 Correct 111 ms 11084 KB Output is correct
6 Correct 113 ms 11084 KB Output is correct
7 Correct 54 ms 8392 KB Output is correct
8 Correct 970 ms 27476 KB Output is correct
9 Correct 215 ms 14008 KB Output is correct
10 Correct 44 ms 8008 KB Output is correct
11 Correct 128 ms 10916 KB Output is correct
12 Correct 39 ms 8728 KB Output is correct
13 Correct 36 ms 7860 KB Output is correct
14 Correct 910 ms 27856 KB Output is correct
15 Correct 882 ms 27908 KB Output is correct

Subtask #3
0 / 16.0

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