제출 #939894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
939894		AdamGS	봉쇄 시간 (IOI23_closing)	C++17	8 / 100	120 ms	42272 KiB

closing

#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
vector<pair<ll,ll>>V[LIM];
ll odl[LIM][2], czy[LIM], n;
void DFS(int x, int o, int k) {
  for(auto i : V[x]) if(i.st!=o) {
    odl[i.st][k]=odl[x][k]+i.nd;
    DFS(i.st, x, k);
  }
}
int max_score(int _N, int x, int y, ll k, vector<int>_U, vector<int>_V, vector<int>_W) {
  n=_N;
  rep(i, n) {
    V[i].clear();
    odl[i][0]=odl[i][1]=czy[i]=0;
  }
  rep(i, n-1) {
    V[_U[i]].pb({_V[i], _W[i]});
    V[_V[i]].pb({_U[i], _W[i]});
  }
  DFS(x, x, 0);
  DFS(y, y, 1);
  vector<ll>P;
  ll sum1=0;
  int ans1=0;
  rep(i, n) {
    if(odl[i][0]>odl[i][1]) swap(odl[i][0], odl[i][1]);
    odl[i][1]-=odl[i][0];
    P.pb(odl[i][0]);
  }
  sort(all(P));
  for(auto i : P) if(sum1+i<=k) {
    sum1+=i;
    ++ans1;
  }
  return ans1;
}

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