oj.uz

답안 #1061332

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1061332 2024-08-16T08:06:34 Z mychecksedad 봉쇄 시간 (IOI23_closing) C++17
0 / 100
 47 ms 10332 KB 
#include "closing.h"
#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 = 6005;
const ll INF = 1e18;

int sz[N];
vector<pair<int, ll>> g[N];
ll val1[N], val2[N], dp[N][N];
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;
}
void p(int v, int pp){
  sz[v] = 1;
  for(auto U: g[v]){
    int u = U.ff;
    if(u != pp && val2[u] != -1){
      p(u, v);
      sz[v] += sz[u];
    }
  }
}
void calc(int v, int p){
  dp[v][0] = 0;
  dp[v][1] = (val1[v] == -1 ? INF: val1[v]);
  // dp[v][2] = (val2[v] == -1 ? INF : val2[v]) + val1[v];
  for(int j = 2; j <= sz[v]*2; ++j) dp[v][j] = INF;
  sz[v] = 1;
  for(auto U: g[v]){
    int u = U.ff;
    if(u != p && val1[u] != -1){
      calc(u, v);
      sz[v] += sz[u];
      for(int j = sz[v]; j >= 1; --j){
        for(int l = 1; l <= min(j, sz[u]); ++l){
          dp[v][j] = min(dp[v][j], dp[v][j - l] + dp[u][l]);
        }
      }
    }
  }
  // cout << v << ":\n";
  // for(int j = 0; j <= 2*sz[v]; ++j) cout << dp[v][j] << ' ';
  //   cout << '\n';
  // cout << v << ' ' << sz[v] << '\n';
}

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;

  for(int i = 0; i < n; ++i){
    if(s[i]){
      val1[i] = -1; //max(D1[i], D2[i]) - min(D1[i], D2[i]);
      val2[i] = max(D1[i], D2[i]) - min(D1[i], D2[i]);
      K -= min(D1[i], D2[i]);
    }else{
      val1[i] = min(D1[i], D2[i]);
      val2[i] = max(D1[i], D2[i]) - val1[i];
    }
  }
  if(K<0) return anss;
  for(int v: euler){
    p(v, v);
    calc(v, v);
    // cout << sz[v] << ' ';
    for(int i = 2*sz[v]; i >= 0; --i){
      for(int j = 1; j <= (i+1)/2; ++j){
        if(i-j<0) break;
        dp[v][i] = min(dp[v][i], dp[v][i - j] + val2[v] * j);
      }
    }
    
  }
  vector<ll> DP(2*n + 5, INF);
  DP[0] = 0;
  int S = 0;
  for(int u: euler){
    S += sz[u]*2;
    assert(S <= 2*n+4);
    for(int j = S; j >= 1; --j){
      for(int l = 1; l <= min(sz[u]*2, 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 max(i + int(euler.size()), anss);
    }
  }

  return anss;
}

Compilation message

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for(int i = 0; i < A.size(); ++i){
      |                  ~~^~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct

Subtask #1
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 47 ms 10332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Runtime error 5 ms 4860 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Runtime error 5 ms 4860 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Runtime error 5 ms 4860 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Runtime error 5 ms 4860 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Runtime error 5 ms 4860 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Runtime error 5 ms 4860 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Runtime error 5 ms 4860 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Runtime error 5 ms 4860 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -