Submission #1178071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178071		Kaztaev_Alisher	Closing Time (IOI23_closing)	C++20	21 / 100	1097 ms	24900 KiB

closing

#include <bits/stdc++.h>

#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second

using namespace std;
using ll = long long;

const ll N = 2e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7;

ll dp[2][N] , a[N] , b[N] , c[N];
vector<ll> g[N];

int solve(ll n , ll x , ll y , ll k){
	for(ll i = 1; i <= n; i++) g[i].clear();
	for(ll i = 1; i < n; i++){
		g[a[i]].push_back(i);
		g[b[i]].push_back(i);
	}
	if(x > y) swap(x,y);
	for(ll i = 0; i < 2; i++){
		for(ll j = 1; j <= n; j++){
			dp[i][j] = inf;
		}
		set<pair<ll,ll>> st;
		if(i == 0) dp[i][x] = 0 , st.insert({0,x});
		else dp[i][y] = 0 , st.insert({0,y});
		while(st.size()){
			ll v = st.begin()->S;
			st.erase(st.begin());
			for(ll k : g[v]){
				ll to = (a[k]^b[k]^v);
				if(dp[i][to] > dp[i][v] + c[k]){
					st.erase({dp[i][to],to});
					dp[i][to] = dp[i][v] + c[k];
					st.insert({dp[i][to],to});
				}
			}
		}
	}
	int cur = 0;
	for(int l = 1; l <= n; l++){
		for(int r = l; r <= n; r++){
			if(l <= x && x <= r){
				for(int i = 1; i <= n; i++) c[i] = 0;
				for(int i = l; i <= r; i++) c[i] = dp[0][i];
				for(int i = r+1; i <= y; i++) if(c[i] < dp[1][i]) c[i] = dp[1][i];
				ll bar = k;
				for(int i = 1; i <= n; i++) bar -= c[i];
				for(int i = r , j = y+1;;){
					if(i >= 1 && j <= n){
						if(max(dp[1][i]-c[i] , 0ll) <= max(dp[1][j]-c[j] , 0ll) && bar-max(dp[1][i]-c[i] , 0ll) >= 0){
							bar -= max(dp[1][i]-c[i] , 0ll);
							c[i] = max(dp[1][i] , c[i]);
							i--;
						} else if(bar-max(dp[1][j]-c[j] , 0ll) >= 0){
							bar -= max(dp[1][j]-c[j] , 0ll);
							c[j] = max(dp[1][j] , c[j]);
							j++;
						} else {
							break;
						}
					} else if(i >= 1){
						if(bar-max(dp[1][i]-c[i] , 0ll) >= 0){
							bar -= max(dp[1][i]-c[i] , 0ll);
							c[i] = max(dp[1][i] , c[i]);
							i--;
						} else {
							break;
						} 
					} else if(j <= n){
						if(bar-max(dp[1][j]-c[j] , 0ll) >= 0){
							bar -= max(dp[1][j]-c[j] , 0ll);
							c[j] = max(dp[1][j] , c[j]);
							j++;
						} else {
							break;
						}	
					} else {
						break;
					}
					
				}
				bar = 0;
				for(int i = 1; i <= n; i++){
					bar += c[i];
				}
				if(bar <= k){
					int ans = 0;
					for(int i = x; i <= n; i++){
						if(c[i] >= dp[0][i]) ans++;
						else break;
					}
					for(int i = x-1; i >= 1; i--){
						if(c[i] >= dp[0][i]) ans++;
						else break;
					}
					for(int i = y; i <= n; i++){
						if(c[i] >= dp[1][i]) ans++;
						else break;
					}
					for(int i = y-1; i >= 1; i--){
						if(c[i] >= dp[1][i]) ans++;
						else break;
					}
					cur = max(cur , ans);
				}
				
				bar = k;
				for(int i = 1; i <= n; i++) c[i] = 0;
				for(int i = l; i <= r; i++) c[i] = dp[0][i] , bar -= c[i];
				
				for(int i = y-1 , j = y+1;;){
					if(i >= 1 && j <= n){
						if(max(dp[1][i]-c[i] , 0ll) <= max(dp[1][j]-c[j] , 0ll) && bar-max(dp[1][i]-c[i] , 0ll) >= 0){
							bar -= max(dp[1][i]-c[i] , 0ll);
							c[i] = max(dp[1][i] , c[i]);
							i--;
						} else if(bar-max(dp[1][j]-c[j] , 0ll) >= 0){
							bar -= max(dp[1][j]-c[j] , 0ll);
							c[j] = max(dp[1][j] , c[j]);
							j++;
						} else {
							break;
						}
					} else if(i >= 1){
						if(bar-max(dp[1][i]-c[i] , 0ll) >= 0){
							bar -= max(dp[1][i]-c[i] , 0ll);
							c[i] = max(dp[1][i] , c[i]);
							i--;
						} else {
							break;
						} 
					} else if(j <= n){
						if(bar-max(dp[1][j]-c[j] , 0ll) >= 0){
							bar -= max(dp[1][j]-c[j] , 0ll);
							c[j] = max(dp[1][j] , c[j]);
							j++;
						} else {
							break;
						}	
					} else {
						break;
					}
					
				}
				if(bar >= 0){
					int ans = 0;
					for(int i = x; i <= n; i++){
						if(c[i] >= dp[0][i]) ans++;
						else break;
					}
					for(int i = x-1; i >= 1; i--){
						if(c[i] >= dp[0][i]) ans++;
						else break;
					}
					for(int i = y; i <= n; i++){
						if(c[i] >= dp[1][i]) ans++;
						else break;
					}
					for(int i = y-1; i >= 1; i--){
						if(c[i] >= dp[1][i]) ans++;
						else break;
					}
					cur = max(cur , ans);
				}
			}
		}
	}
	return cur;
}
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W){
	for(int i = 0; i < N; i++){
		a[i+1] = U[i]+1; 
		b[i+1] = V[i]+1; 
		c[i+1] = W[i]; 
	}
	return solve(N , X+1 , Y+1 , K);
}
// int main()
// {
// 
    // int Q;
    // assert(1 == scanf("%d", &Q));
// 
    // std::vector<int> N(Q), X(Q), Y(Q);
    // std::vector<long long> K(Q);
    // std::vector<std::vector<int>> U(Q), V(Q), W(Q);
// 
    // for (int q = 0; q < Q; q++)
    // {
        // assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));
// 
        // U[q].resize(N[q] - 1);
        // V[q].resize(N[q] - 1);
        // W[q].resize(N[q] - 1);
        // for (int i = 0; i < N[q] - 1; ++i)
        // {
            // assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
        // }
    // }
    // fclose(stdin);
// 
    // std::vector<int> result(Q);
    // for (int q = 0; q < Q; q++)
    // {
        // result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
    // }
// 
    // for (int q = 0; q < Q; q++)
    // {
        // printf("%d\n", result[q]);
    // }
    // fclose(stdout);
// 
    // return 0;
// }

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17