oj.uz

Submission #1064237

# Submission time Handle Problem Language Result Execution time Memory
1064237 2024-08-18T10:43:16 Z DorostWef Closing Time (IOI23_closing) C++17
0 / 100
 154 ms 49656 KB 
#include "closing.h"

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N = 200003;
vector <pair <int, int>> g[N];
vector <int> ss[2][N];
ll dis[2][N];
int par[2][N];
int in[N];

void dij (int id, int v, int p) {
	for (auto [u, w] : g[v]) {
		if (u != p) {
			dis[id][u] = dis[id][v] + w;
			par[id][u] = v;
			ss[id][v].push_back(u);
			dij (id, u, v);
		}
	}
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    //cout << "------------" << endl;
	int n = N, m = (int)U.size();
	for (int i = 0; i < n; i++) {
		in[i] = 0;
		g[i].clear();
		ss[0][i].clear();
		ss[1][i].clear();
	}
	for (int i = 0; i < m; i++) {
		g[U[i]].push_back(make_pair (V[i], W[i]));
		g[V[i]].push_back(make_pair (U[i], W[i]));
	}
	dis[0][X] = 0;
	par[0][X] = -1;
	dij (0, X, X);
	dis[1][Y] = 0;
	par[1][Y] = -1;
	dij (1, Y, Y);
//	for (int i = 0; i < n; i++) {
//		cout << i << ' ' << dis[0][i] << ' ' << dis[1][i] << endl;
//	}
	set <pair <ll, int>> st;
	for (int i = 0; i < n; i++) {
		if (dis[0][i] < dis[1][i]) {
			if (par[0][i] == -1)
				st.insert (make_pair (dis[0][i], i));
		} else {
			if (par[1][i] == -1)
				st.insert (make_pair (dis[1][i], i));
		}
	}
	int ans = 0;
	while (!st.empty()) {
		int x = ((*st.begin()).S);
		st.erase ((*st.begin()));
		int i = x;
		//cout << i << endl;
		if (in[x] == 0) {
			if (dis[0][i] < dis[1][i]) {
				in[x] ^= 1;
				if (K >= dis[0][i]) {
					K -= dis[0][i];
					ans++;
				}
				for (int u : ss[0][x]) {
					if (in[u] % 2 == 0) {
						if (dis[0][u] < dis[1][u])
							st.insert (make_pair (dis[0][u], u));
						else if (in[u] == 2) {
							st.insert (make_pair (dis[0][u] - dis[1][u], u));
						}
					}
				}
				if (in[par[1][i]] >= 2)
					st.insert (make_pair (dis[1][i] - dis[0][i], i));
			} else {
				in[x] ^= 2;
				if (K >= dis[1][i]) {
					K -= dis[1][i];
					ans++;
				}
				for (int u : ss[1][x]) {
					if (in[u] < 2) {
						if (dis[1][u] < dis[0][u])
							st.insert (make_pair (dis[1][u], u));
						else if (in[u] == 1) {
							st.insert (make_pair (dis[1][u] - dis[0][u], u));
						}
					}
				}
				if (in[par[0][i]] % 2)
					st.insert (make_pair (dis[0][i] - dis[1][i], i));
			}	
		} else {
			if (dis[0][i] > dis[1][i]) {
				in[x] ^= 1;
				int w = dis[0][i] - dis[1][i];
				if (K >= w) {
					K -= w;
					ans++;
				}
				for (int u : ss[0][x]) {
					if (in[u] % 2 == 0) {
						if (dis[0][u] < dis[1][u])
							st.insert (make_pair (dis[0][u], u));
						else if (in[u] == 2) {
							st.insert (make_pair (dis[0][u] - dis[1][u], u));
						}
					}
				}
			} else {
				in[x] ^= 2;
				int w = dis[1][i] - dis[0][i];
				if (K >= w) {
					K -= w;
					ans++;
				}
				for (int u : ss[1][x]) {
					if (in[u] < 2) {
						if (dis[1][u] < dis[0][u])
							st.insert (make_pair (dis[1][u], u));
						else if (in[u] == 1) {
							st.insert (make_pair (dis[1][u] - dis[0][u], u));
						}
					}
				}
			}	
		}
	}
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 154 ms 49656 KB 1st lines differ - on the 1st token, expected: '451', found: '187864'
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Incorrect 6 ms 14428 KB 1st lines differ - on the 1st token, expected: '30', found: '35'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Incorrect 6 ms 14428 KB 1st lines differ - on the 1st token, expected: '30', found: '35'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Incorrect 6 ms 14428 KB 1st lines differ - on the 1st token, expected: '30', found: '35'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Incorrect 6 ms 14428 KB 1st lines differ - on the 1st token, expected: '30', found: '35'
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Incorrect 6 ms 14428 KB 1st lines differ - on the 1st token, expected: '30', found: '35'
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Incorrect 6 ms 14428 KB 1st lines differ - on the 1st token, expected: '30', found: '35'
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Incorrect 6 ms 14428 KB 1st lines differ - on the 1st token, expected: '30', found: '35'
4 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Incorrect 6 ms 14428 KB 1st lines differ - on the 1st token, expected: '30', found: '35'
4 Halted 0 ms 0 KB -