oj.uz

Submission #1065566

# Submission time Handle Problem Language Result Execution time Memory
1065566 2024-08-19T09:23:27 Z mychecksedad Closing Time (IOI23_closing) C++17
43 / 100
 132 ms 51432 KB 
#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;
    }
  }
  // cout << K << '\n';
  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);
      if(K >= val1[idx]){
        best = max(best, (int)get(0, d-1, 1, K - val1[idx]).ss + 1);
      }
      upd(0, d-1, i, 1, vals[i][0], 2);
    }
    if(co == 4){
      upd(0, d-1, i, 1, 0, 0);
      if(K >= val1[idx]){
        best = max(best, (int)get(0, d-1, 1, K - val1[idx]).ss + 1);
      }
      upd(0, d-1, i, 1, vals[i][0] / 2, 1);
    }
    if(co == 1 && val2[idx] >= val1[idx]){
      upd(0, d-1, i, 1, 0, 0);
      if(K >= val1[idx]){
        best = max(best, (int)get(0, d-1, 1, K - val1[idx]).ss + 1);
      }
      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);
}

Compilation message

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:152: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]
  152 |   for(int i = 0; i < vals.size(); ++i){
      |                  ~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7256 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 51432 KB Output is correct
2 Correct 130 ms 50896 KB Output is correct
3 Correct 71 ms 10240 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7260 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 4 ms 7260 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7308 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 4 ms 7260 KB Output is correct
9 Correct 4 ms 7260 KB Output is correct
10 Correct 3 ms 7260 KB Output is correct
11 Correct 3 ms 7516 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7260 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 4 ms 7260 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7308 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 4 ms 7260 KB Output is correct
9 Correct 4 ms 7260 KB Output is correct
10 Correct 3 ms 7260 KB Output is correct
11 Correct 3 ms 7516 KB Output is correct
12 Correct 4 ms 7516 KB Output is correct
13 Correct 4 ms 7516 KB Output is correct
14 Correct 4 ms 7512 KB Output is correct
15 Correct 4 ms 7512 KB Output is correct
16 Correct 3 ms 7516 KB Output is correct
17 Correct 3 ms 7516 KB Output is correct
18 Correct 3 ms 7516 KB Output is correct
19 Correct 3 ms 7496 KB Output is correct
20 Correct 6 ms 7516 KB Output is correct
21 Correct 5 ms 7516 KB Output is correct
22 Correct 5 ms 7516 KB Output is correct
23 Correct 3 ms 7512 KB Output is correct
24 Correct 4 ms 7516 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7260 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 4 ms 7260 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7308 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 4 ms 7260 KB Output is correct
9 Correct 4 ms 7260 KB Output is correct
10 Correct 3 ms 7260 KB Output is correct
11 Correct 3 ms 7516 KB Output is correct
12 Correct 4 ms 7516 KB Output is correct
13 Correct 4 ms 7516 KB Output is correct
14 Correct 4 ms 7512 KB Output is correct
15 Correct 4 ms 7512 KB Output is correct
16 Correct 3 ms 7516 KB Output is correct
17 Correct 3 ms 7516 KB Output is correct
18 Correct 3 ms 7516 KB Output is correct
19 Correct 3 ms 7496 KB Output is correct
20 Correct 6 ms 7516 KB Output is correct
21 Correct 5 ms 7516 KB Output is correct
22 Correct 5 ms 7516 KB Output is correct
23 Correct 3 ms 7512 KB Output is correct
24 Correct 4 ms 7516 KB Output is correct
25 Correct 5 ms 7516 KB Output is correct
26 Correct 6 ms 8496 KB Output is correct
27 Correct 6 ms 8524 KB Output is correct
28 Correct 5 ms 8156 KB Output is correct
29 Correct 5 ms 8284 KB Output is correct
30 Correct 5 ms 8284 KB Output is correct
31 Correct 4 ms 8072 KB Output is correct
32 Correct 5 ms 8284 KB Output is correct

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7256 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 3 ms 7260 KB Output is correct
4 Correct 4 ms 7260 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7308 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 3 ms 7260 KB Output is correct
9 Incorrect 3 ms 7260 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
10 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7256 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 3 ms 7260 KB Output is correct
4 Correct 4 ms 7260 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7308 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 4 ms 7260 KB Output is correct
10 Correct 4 ms 7260 KB Output is correct
11 Correct 3 ms 7260 KB Output is correct
12 Correct 3 ms 7516 KB Output is correct
13 Correct 4 ms 7516 KB Output is correct
14 Correct 4 ms 7516 KB Output is correct
15 Correct 4 ms 7512 KB Output is correct
16 Correct 4 ms 7512 KB Output is correct
17 Correct 3 ms 7516 KB Output is correct
18 Correct 3 ms 7516 KB Output is correct
19 Correct 3 ms 7516 KB Output is correct
20 Correct 3 ms 7260 KB Output is correct
21 Incorrect 3 ms 7260 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
22 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7256 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 3 ms 7260 KB Output is correct
4 Correct 4 ms 7260 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7308 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 4 ms 7260 KB Output is correct
10 Correct 4 ms 7260 KB Output is correct
11 Correct 3 ms 7260 KB Output is correct
12 Correct 3 ms 7516 KB Output is correct
13 Correct 4 ms 7516 KB Output is correct
14 Correct 4 ms 7516 KB Output is correct
15 Correct 4 ms 7512 KB Output is correct
16 Correct 4 ms 7512 KB Output is correct
17 Correct 3 ms 7516 KB Output is correct
18 Correct 3 ms 7516 KB Output is correct
19 Correct 3 ms 7516 KB Output is correct
20 Correct 3 ms 7496 KB Output is correct
21 Correct 6 ms 7516 KB Output is correct
22 Correct 5 ms 7516 KB Output is correct
23 Correct 5 ms 7516 KB Output is correct
24 Correct 3 ms 7512 KB Output is correct
25 Correct 4 ms 7516 KB Output is correct
26 Correct 3 ms 7516 KB Output is correct
27 Correct 3 ms 7260 KB Output is correct
28 Incorrect 3 ms 7260 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
29 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7256 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 3 ms 7260 KB Output is correct
4 Correct 4 ms 7260 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7308 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 4 ms 7260 KB Output is correct
10 Correct 4 ms 7260 KB Output is correct
11 Correct 3 ms 7260 KB Output is correct
12 Correct 3 ms 7516 KB Output is correct
13 Correct 4 ms 7516 KB Output is correct
14 Correct 4 ms 7516 KB Output is correct
15 Correct 4 ms 7512 KB Output is correct
16 Correct 4 ms 7512 KB Output is correct
17 Correct 3 ms 7516 KB Output is correct
18 Correct 3 ms 7516 KB Output is correct
19 Correct 3 ms 7516 KB Output is correct
20 Correct 3 ms 7496 KB Output is correct
21 Correct 6 ms 7516 KB Output is correct
22 Correct 5 ms 7516 KB Output is correct
23 Correct 5 ms 7516 KB Output is correct
24 Correct 3 ms 7512 KB Output is correct
25 Correct 4 ms 7516 KB Output is correct
26 Correct 5 ms 7516 KB Output is correct
27 Correct 6 ms 8496 KB Output is correct
28 Correct 6 ms 8524 KB Output is correct
29 Correct 5 ms 8156 KB Output is correct
30 Correct 5 ms 8284 KB Output is correct
31 Correct 5 ms 8284 KB Output is correct
32 Correct 4 ms 8072 KB Output is correct
33 Correct 5 ms 8284 KB Output is correct
34 Correct 3 ms 7516 KB Output is correct
35 Correct 3 ms 7260 KB Output is correct
36 Incorrect 3 ms 7260 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
37 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7256 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 3 ms 7260 KB Output is correct
4 Correct 4 ms 7260 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7308 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 4 ms 7260 KB Output is correct
10 Correct 4 ms 7260 KB Output is correct
11 Correct 3 ms 7260 KB Output is correct
12 Correct 3 ms 7516 KB Output is correct
13 Correct 4 ms 7516 KB Output is correct
14 Correct 4 ms 7516 KB Output is correct
15 Correct 4 ms 7512 KB Output is correct
16 Correct 4 ms 7512 KB Output is correct
17 Correct 3 ms 7516 KB Output is correct
18 Correct 3 ms 7516 KB Output is correct
19 Correct 3 ms 7516 KB Output is correct
20 Correct 3 ms 7496 KB Output is correct
21 Correct 6 ms 7516 KB Output is correct
22 Correct 5 ms 7516 KB Output is correct
23 Correct 5 ms 7516 KB Output is correct
24 Correct 3 ms 7512 KB Output is correct
25 Correct 4 ms 7516 KB Output is correct
26 Correct 5 ms 7516 KB Output is correct
27 Correct 6 ms 8496 KB Output is correct
28 Correct 6 ms 8524 KB Output is correct
29 Correct 5 ms 8156 KB Output is correct
30 Correct 5 ms 8284 KB Output is correct
31 Correct 5 ms 8284 KB Output is correct
32 Correct 4 ms 8072 KB Output is correct
33 Correct 5 ms 8284 KB Output is correct
34 Correct 3 ms 7516 KB Output is correct
35 Correct 3 ms 7260 KB Output is correct
36 Incorrect 3 ms 7260 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
37 Halted 0 ms 0 KB -