제출 #1065520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1065520		mychecksedad	봉쇄 시간 (IOI23_closing)	C++17	43 / 100	126 ms	54448 KiB

closing

#include "closing.h"
// #pragma optimize ("O3")
// #pragma target ("avx2")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long
#define ff first
#define ss second
const int N = 3e5+10;
const ll INF = 1e18;
 
int sz[N];
vector<pair<int, ll>> g[N];
ll val1[N], val2[N], T[N][2];
void build(int l, int r, int k){
  if(l == r){
    T[k][0] = 0;
    T[k][1] = 0;
    return;
  }
  int m = l+r>>1;
  build(l, m, k<<1);
  build(m+1, r, k<<1|1);
  T[k][0] = 0;
  T[k][1] = 0;
}
void upd(int l, int r, int p, int k, ll val, int co){
  if(l == r){
    T[k][0] = val;
    T[k][1] = co;
    return;
  }
  int m = l+r>>1;
  if(p <= m) upd(l, m, p, k<<1, val, co);
  else upd(m+1, r, p, k<<1|1, val, co);
  T[k][0] = T[k<<1][0] + T[k<<1|1][0];
  T[k][1] = T[k<<1][1] + T[k<<1|1][1];
}
pair<ll, ll> get(int l, int r, int k, ll R){
  if(R >= T[k][0]) return {T[k][0], T[k][1]};
  if(l == r){
    return {0ll, 0ll};
  }
  int m = l+r>>1;
  pair<ll, ll> ans = {0ll, 0ll};
  if(T[k<<1][0] <= R){
    ans = get(l, m, k<<1, R);
  }else{
    return get(l, m, k<<1, R);
  }
  R -= ans.ff;
  auto x = get(m+1, r, k<<1|1, R);
  return {x.ff + ans.ff, x.ss + ans.ss};
}
void dfs(int v, int p, vector<ll> &D){
  for(auto U: g[v]){
    int u = U.ff;
    if(u != p){
      D[u] = D[v] + U.ss;
      dfs(u, v, D);
    }
  }
}
vector<int> euler;
bool pre(int v, int p, int t){
  euler.pb(v);
  if(v == t){
    return 1;
  }
  for(auto U: g[v]){
    int u = U.ff;
    if(u != p){
      bool ok = pre(u, v, t);
      if(ok) return 1;
    }
  }
  euler.pop_back();
  return 0;
}


int max_score(int n, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W){
  for(int i = 0; i < n; ++i) g[i].clear();
  euler.clear();
  for(int i = 0; i < n - 1; ++i){
    g[V[i]].pb({U[i], W[i]});
    g[U[i]].pb({V[i], W[i]});
  }
  if(X > Y) swap(X,Y);
  vector<ll> D1(n), D2(n);
  dfs(X, X, D1);
  dfs(Y, Y, D2);
 
 
  vector<ll> A;
  for(int i =0 ; i < n; ++i) A.pb(D1[i]); 
  for(int i =0 ; i < n; ++i) A.pb(D2[i]); 
  sort(all(A));
  int anss = 0; ll tot = 0;
  for(int i = 0; i < A.size(); ++i){
    if(tot + A[i] <= K) tot += A[i], ++anss;
  }
 
  pre(X, X, Y);
  vector<bool> s(n);
  for(int v: euler) s[v] = 1;

  vector<array<ll, 3>> vals;
 
  for(int i = 0; i < n; ++i){
    if(s[i]){
      val1[i] = max(D1[i], D2[i]) - min(D1[i], D2[i]);
      val2[i] = -1;
      K -= min(D1[i], D2[i]);
      vals.pb({2*val1[i], i, 4});
    }else{
      val1[i] = min(D1[i], D2[i]);
      val2[i] = max(D1[i], D2[i]) - val1[i];
      vals.pb({2*val1[i], i, 1});
      if(val2[i] < val1[i]){
        vals.pb({val1[i]+val2[i], i, 3});
      }else{
        vals.pb({2*val2[i], i, 2});
      }
    }
  }
  if(K<0) return anss;
  // cout << K << ' ';
  sort(all(vals));
  vector<int> used(n);
  int d = vals.size();
  build(0, d-1, 1);
  for(int i = 0; i < vals.size(); ++i){
    int idx = vals[i][1];
    int co = vals[i][2];
    if(co == 3){
      upd(0, d-1, i, 1, vals[i][0], 2);
      used[idx] = 1;
    }else if(co == 4){
      upd(0, d-1, i, 1, vals[i][0] / 2, 1);
    }else if(co == 2 || (co == 1 && !used[idx])){
      upd(0, d-1, i, 1, vals[i][0] / 2, 1);
    }else if(co == 1 && used[idx]){
      used[idx] = i;
    }
  }
  int best = get(0, d-1, 1, K).ss;

  for(int i = 0; i < vals.size(); ++i){
    // cout << vals[i][0] << ' ' <<vals[i][1] << ' ' <<vals[i][2] << '\n';
    int idx = vals[i][1];
    int co = vals[i][2];
    if(co == 3){
      upd(0, d-1, i, 1, 0, 0);
      // cout << idx << ' ' << val1[idx] << '\n';
      // upd(0, d-1, used[idx], 1, val1[idx], 1);
      if(K >= val1[idx]){
        best = max(best, (int)get(0, d-1, 1, K - val1[idx]).ss + 1);
        // cout << idx << '\n';
      }
      upd(0, d-1, i, 1, vals[i][0], 2);
    }
    if(co == 4){
      upd(0, d-1, i, 1, 0, 0);
      // cout << idx << ' ' << val1[idx] << '\n';
      // upd(0, d-1, used[idx], 1, val1[idx], 1);
      if(K >= val1[idx]){
        best = max(best, (int)get(0, d-1, 1, K - val1[idx]).ss + 1);
        // cout << idx << '\n';
        // cout << best << ' ' << (int)get(0, d-1, 1, K - val1[idx]).ff << '\n';
      }
      upd(0, d-1, i, 1, vals[i][0] / 2, 1);
    }
  }
  // for(int i = 0; i < n; ++i){
  //   cout << val1[i] << ' ' << val2[i] << '\n';
  // }
  return max(best+int(euler.size()), anss);
  // for(int v: euler){
  //   p(v, v);
  //   calc(v, v);
  // }
  // for(int u: euler){
  //   for(int j = 2; j <= sz[u]; ++j){
  //     assert(dp[u][j] - dp[u][j - 1] >= dp[u][j - 1] - dp[u][j - 2]);
  //   }
  // }
  // int ans = 0;
  // ll ls = 0, rs = 1e18;
  // while(ls <= rs){
  //   ll lm = ls+rs>>1;
  //   int num = 0;
  //   ll cost = 0;
  //   for(int u: euler){  
  //     for(int j = 1; j <= sz[u]; ++j){
  //       if(dp[u][j] - dp[u][j - 1] <= lm){
  //         cost += dp[u][j] - dp[u][j - 1];
  //         ++num;
  //         if(cost <= K){
  //           ans = max(ans, num);
  //         }
  //       }
  //     }
  //   }
  //   if(cost > K){
  //     rs = lm - 1;
  //   }else{
  //     ls = lm + 1;
  //   }
  // }

  // vector<ll> DP(2*n + 5, INF);
  // DP[0] = 0;
  // int S = 0;
  // for(int u: euler){
  //   S += sz[u];
  //   for(int j = S; j >= 1; --j){
  //     for(int l = 1; l <= min(sz[u], j); ++l){
  //       DP[j] = min(DP[j], DP[j - l] + dp[u][l]);
  //     }
  //   }
  // }
  // for(int i = 2*n; i >= 0; --i){
    // if(DP[i] <= K){
    // }
  // }
 
  // return anss;
}

컴파일 시 표준 에러 (stderr) 메시지

closing.cpp: In function 'void build(int, int, int)':
closing.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   int m = l+r>>1;
      |           ~^~
closing.cpp: In function 'void upd(int, int, int, int, long long int, int)':
closing.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int m = l+r>>1;
      |           ~^~
closing.cpp: In function 'std::pair<long long int, long long int> get(int, int, int, long long int)':
closing.cpp:46:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   int m = l+r>>1;
      |           ~^~
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for(int i = 0; i < A.size(); ++i){
      |                  ~~^~~~~~~~~~
closing.cpp:135:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |   for(int i = 0; i < vals.size(); ++i){
      |                  ~~^~~~~~~~~~~~~
closing.cpp:151:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |   for(int i = 0; i < vals.size(); ++i){
      |                  ~~^~~~~~~~~~~~~

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