oj.uz

Submission #801754

# Submission time Handle Problem Language Result Execution time Memory
801754 2023-08-02T07:29:26 Z SanguineChameleon Travelling Merchant (CCO21_day2problem1) C++17
0 / 25
 2000 ms 25528 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 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 61 ms 5244 KB Output is correct
9 Incorrect 4 ms 5076 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 11824 KB Output is correct
2 Correct 153 ms 11808 KB Output is correct
3 Correct 56 ms 9016 KB Output is correct
4 Correct 48 ms 7516 KB Output is correct
5 Correct 144 ms 11028 KB Output is correct
6 Correct 157 ms 11116 KB Output is correct
7 Correct 52 ms 8392 KB Output is correct
8 Execution timed out 2093 ms 25528 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

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