oj.uz

Submission #847332

# Submission time Handle Problem Language Result Execution time Memory
847332 2023-09-09T13:42:00 Z sofapuden Closing Time (IOI23_closing) C++17
8 / 100
 144 ms 34428 KB 
#include <bits/stdc++.h>
#include "closing.h"

using namespace std;

typedef long long ll;

vector<int> Ylist;
vector<ll> disx, disy;
int amTak = 0;

int dijkstra(int X, int Y, vector<array<int,2>> vis, int tak, vector<vector<pair<int,int>>> &gr, ll K){
	priority_queue<pair<ll,pair<int,int>>> pq;
	for(int i = 0; i < (int)vis.size(); ++i){
		if(vis[i][0] && vis[i][1]){
			for(auto x : gr[i])if(!vis[x.first][0] && !vis[x.first][1])pq.push({max(-disx[x.first],disy[x.first]),{x.first,0}});
		}
	}
	int ret = 0;
	for(int i = 0; i < tak; ++i){
		if(!pq.size()){ amTak = i; break; }
		auto x = pq.top();
		pq.pop();
		if(K + x.first < 0){ amTak = i; break; }
		vis[x.first][0] = vis[x.first][1] = 1;
		K+=x.first;
		ret += 2;
		for(auto y : gr[x.second.first])if(!vis[y.first][0] && !vis[y.first][1])pq.push({max(-disx[y.first],disy[y.first]),{y.first,0}});
	}
	amTak = tak;
	while(pq.size())pq.pop();
	for(int i = 0; i < (int)vis.size(); ++i){
		if(vis[i][0])for(auto x : gr[i])if(!vis[x.first][0])pq.push({-disx[x.first],{x.first,0}});
		if(vis[i][1])for(auto x : gr[i])if(!vis[x.first][1])pq.push({-disy[x.first],{x.first,1}});
	}
	while(pq.size()){
		auto x = pq.top();
		pq.pop();
		if(vis[x.second.first][0] || vis[x.second.first][1])continue;
		vis[x.second.first][x.second.second] = 1;
		if(K + x.first < 0)break;
		K+=x.first;
		ret++;
		for(auto y : gr[x.second.first]){
			if(x.second.second == 0){
				pq.push(make_pair(-disx[y.first], make_pair(y.first, x.second.second)));
			}
			else{
				pq.push(make_pair(-disy[y.first], make_pair(y.first, x.second.second)));
			}
		}
	}
	return ret;
}


void fil(int X, int p, vector<ll> &dis, vector<vector<pair<int,int>>> &gr){
	for(auto y : gr[X]){
		if(y.first == p)continue;
		dis[y.first] = dis[X] + y.second;
		fil(y.first,X,dis,gr);
	}
}

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W){
	vector<vector<pair<int,int>>> gr(N);
	for(int i = 0; i < N - 1; ++i){
		gr[U[i]].emplace_back(V[i], W[i]);
		gr[V[i]].emplace_back(U[i], W[i]);
	}
	vector<array<int,2>> vis(N);
	Ylist.clear();
	disx.clear();
	disy.clear();
	disx.resize(N,0);
	disy.resize(N,0);
	fil(X,X,disx,gr);
	fil(Y,Y,disy,gr);
	int ans = 0;

	// case no vis
	{
		for(int i = 0; i < N; ++i)vis[i][0] = vis[i][1] = 0;
		vis[X][0] = 1;
		vis[Y][1] = 1;
		ans = 2 + dijkstra(X,Y,vis,0,gr,K);
	}

	// case both vis
	{
		for(int i = 0; i < N; ++i)vis[i][0] = vis[i][1] = 0;
		int am = 0;
		int su = disx[Y];
		ll K_cur = K;
		for(int i = 0; i < N; ++i){
			if(disx[i] + disy[i] == su){
				am++;
				K_cur -= min(disx[i], disy[i]);
				if(disx[i] < disy[i])vis[i][0] = 1;
				else vis[i][1] = 1;
			}
		}
		vector<pair<int,int>> val;
		for(int i = 0; i < N; ++i){
			if(disx[i] + disy[i] == su){
				val.emplace_back(abs(disx[i] - disy[i]),i);
			}
		}
		sort(val.begin(),val.end());
		int sz = (int)val.size();
		for(int j = 0; j < sz; ++j){
			am++;
			K_cur -= val[j].first;
			vis[val[j].second][0] = vis[val[j].second][1] = 1;
			if(K_cur > 0){
				dijkstra(X,Y,vis,N,gr,K_cur);
				for(int m = 0; m <= amTak; ++m){
					ans = max(ans,am +  dijkstra(X,Y,vis,m,gr,K_cur));
				}
			}
			else break;
		}
	}

    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 28864 KB Output is correct
2 Correct 144 ms 34428 KB Output is correct
3 Correct 67 ms 2968 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 0 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 0 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 0 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 0 ms 348 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 0 ms 348 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 0 ms 348 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 0 ms 348 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 0 ms 348 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -