Submission #1206572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206572		hyakup	Closing Time (IOI23_closing)	C++20	0 / 100	1097 ms	27176 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5;

using ll = long long;
using pll = pair<ll, int>;

const ll inf = 1e18;

vector<vector<pair<int, int>>> adj;
vector<vector<ll>> dist;
vector<vector<int>> pai;

void init( int n ){
  adj.clear(); adj.resize(n);
  dist.clear(); dist.resize( 2, vector<ll>(n));
  pai.clear(); pai.resize( 2, vector<int>(n));
}

void dfs( int cur, int last, int t ){
  pai[t][cur] = last;
  for( auto [viz, d] : adj[cur] ) if( viz != last ){
    dist[t][viz] = dist[t][cur] + d;
    dfs( viz, cur, t );
  }
}

int max_score(int n, int x, int y, long long k, vector<int> a, vector<int> b, vector<int> c ) {
  init(n);
  int m = a.size();
  for( int i = 0; i < m; i++ ){
    adj[a[i]].push_back({ b[i], c[i] });
    adj[b[i]].push_back({ a[i], c[i] });
  }

  dfs( x, x, 0 );
  dfs( y, y, 1 );

  int resp = 0;
  ll suml = 0;
  for( int l = x; l >= 0; l-- ){
    suml += dist[0][l];
    ll sumr = 0;
    for( int r = y; r < n; r++ ){
      sumr += dist[1][r];
      int px = x + 1, py = y - 1;
      ll sum = 0;
      while( true ){
        ll cx, cy;
        if( px <= py ){
          cx = dist[0][px];
          cy = dist[1][py];
        }
        else{
          cx = dist[0][px] - dist[1][px];
          cy = dist[1][py] - dist[0][py];
        }
        if( cx < l ) cx = inf;
        if( cy > r ) cy = inf;

        if( k < min( cx, cy ) + suml + sumr + sum ){
          resp = max( resp, px - l + r - py );
          break;
        }

        if( cx <= cy ){
          sum += cx;
          px++;
        }
        else{
          sum += cy;
          py--;
        }
      }
    }
  }

  return resp;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 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