oj.uz

Submission #1010197

# Submission time Handle Problem Language Result Execution time Memory
1010197 2024-06-28T13:03:21 Z nickolasarapidis Closing Time (IOI23_closing) C++17
0 / 100
 392 ms 403324 KB 
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int MAXN = 200000;

vector<pair<int, int> > adj[MAXN];

vector<ll> disX(MAXN);
vector<ll> disY(MAXN);

int ans = 0;
int ans2 = 0;

void dfsPrecompute(int s, int e, int X){
	for(auto u : adj[s]){
		if(u.first != e){
			if(X == 0){
				disX[u.first] = disX[s] + u.second;
				dfsPrecompute(u.first, s, X);
			}
			else{
				disY[u.first] = disY[s] + u.second;
				dfsPrecompute(u.first, s, X);
			}
		}
	}
}

void dfs(int s, int e, vector<ll> C, int X){
	ans++;
	for(auto u : adj[s]){
		if(X == 0){
			if(u.first != e and disX[u.first] <= C[u.first]){
				dfs(u.first, s, C, X);
			}
		}
		else{
			if(u.first != e and disY[u.first] <= C[u.first]){
				dfs(u.first, s, C, X);
			}
		}
	}
}

int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W){
	ans = 0; ans2 = 0;
	
	disX.clear();
	disY.clear();
	
	for(int i = 0; i < N; i++){
		adj[i].clear();
	}
	
	for(int i = 0; i < N - 1; i++){
		adj[U[i]].push_back({V[i], W[i]});
		adj[V[i]].push_back({U[i], W[i]});
	}

	vector<tuple<ll, ll, int> > dis(N);

	vector<ll> C(N, 0);
	vector<ll> C2(N, 0);

	disX[X] = 0;
	disY[Y] = 0;

	ll sum = 0;

	dfsPrecompute(X, -1, 0);
	dfsPrecompute(Y, -1, 1);

	for(int i = 0; i < N; i++){
		get<0>(dis[i]) = min(disX[i], disY[i]);
		get<1>(dis[i]) = max(disX[i], disY[i]);
		get<2>(dis[i]) = i;
	}

	sort(dis.begin(), dis.begin() + N - 1);

	for(int i = 0; i < N; i++){
		if(get<2>(dis[i]) != X and get<2>(dis[i]) != Y){
			if(sum + get<0>(dis[i]) <= K){
				if(sum + get<1>(dis[i]) <= K){
					C[get<2>(dis[i])] = get<1>(dis[i]);
					sum += C[get<2>(dis[i])];
				}
				else{
					C[get<2>(dis[i])] = get<0>(dis[i]);
					sum += C[get<2>(dis[i])];
				}
			}
			else{
				break;
			}
		}
	}

	dfs(X, -1, C, 0);
	dfs(Y, -1, C, 1);
	
	ans2 = ans;
	ans = 0;
	
	for(int i = 0; i < N; i++){
		if(sum + get<0>(dis[i]) <= K){
			if(sum + get<1>(dis[i]) <= K){
				C2[get<2>(dis[i])] = get<1>(dis[i]);
				sum += C2[get<2>(dis[i])];
			}
			else{
				C2[get<2>(dis[i])] = get<0>(dis[i]);
				sum += C2[get<2>(dis[i])];
			}
		}
		else{
			break;
		}
	}
	
	dfs(X, -1, C2, 0);
	dfs(Y, -1, C2, 1);

	return max(ans, ans2);
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 157624 KB Output is correct
2 Correct 392 ms 403324 KB Output is correct
3 Incorrect 115 ms 10976 KB 21st lines differ - on the 1st token, expected: '38', found: '25'
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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