oj.uz

Submission #1061451

# Submission time Handle Problem Language Result Execution time Memory
1061451 2024-08-16T09:10:08 Z mychecksedad Closing Time (IOI23_closing) C++17
35 / 100
 37 ms 10068 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 = 3005;
const ll INF = 1e18;
 
int sz[N], par[N];
vector<pair<int, ll>> g[N];
ll val1[N], val2[N], dp[N][N];
void dfs(int v, int p, vector<ll> &D){
  par[v] = p;
  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;
  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]);
    }else{
      val1[i] = min(D1[i], D2[i]);
      val2[i] = max(D1[i], D2[i]) - val1[i];
    }
  }
  if(K<0) return anss;
  // vector<ll> DP(2*n + 5, INF);
  // DP[0] = 0;
  // int S = 0;
  // for(int i = 0; i < n; ++i){
  //   S+=2;
  //   for(int j = S; j >= 1; --j){
  //     DP[j] = min(DP[j], DP[j - 1] + val1[i]);
  //     if(j > 1 && val2[i] != -1)
  //       DP[j] = min(DP[j], DP[j - 2] + val2[i] + val1[i]);
  //   }
  // }
  // for(int i = 2*n; i >= 0; --i){
  //   if(DP[i] <= K){
  //     return max(i + int(euler.size()), anss);
  //   }
  // }
  set<array<ll, 3>> B;
  for(int i = 0; i < n; ++i){
    // if(val2[i] == -1){
    if(val2[i] == -1) B.insert({val1[i] * 2, i, 2});
    else B.insert({val1[i] * 2, i, 1});
    // }
    // else if(val1[i] < val2[i]){
    //   B.pb({val1[i] * 2, 0, 1});
    //   B.pb({val2[i] * 2, 0, 1});
    // }else{
    //   B.pb({val1[i] + val2[i], val1[i], 2});
    // }
  }
  // K *= 2;
  vector<int> taken(n);
  int ans = 0;
  // sort(all(B));
  while(B.size()){
    auto it = B.begin();
    auto x = *it;
    B.erase(it);
    if(taken[x[1]] == 2) continue;
    if(x[2] == 1){
      if(K >= x[0] / 2){
        K -= x[0] / 2;
        ++ans;
        taken[x[1]] = 1;
      }
    }else if(x[2] == 2){
      if(K >= x[0] / 2){
        K -= x[0] / 2;
        ans += 1;
        for(auto U: g[x[1]]){
          int u = U.ff;
          if(u != par[x[1]] && val2[u] != -1){
            if(taken[u]) B.insert({2 * val2[u], u, 2});
            else{
              if(val1[u] <= val2[u])
                B.insert({2 * val2[u], u, 2});
              else B.insert({val1[u] + val2[u], u, 3});
            }
          }
        }
      }
    }else{
      if(K >= x[0]){
        K -= x[0];
        taken[x[1]] = 2;
        ans += 2;
        for(auto U: g[x[1]]){
          int u = U.ff;
          if(u != par[x[1]] && val2[u] != -1){
            if(taken[u]) B.insert({2 * val2[u], u, 2});
            else{
              if(val1[u] <= val2[u])
                B.insert({2 * val2[u], u, 2});
              else B.insert({val1[u] + val2[u], u, 3});
            }
          }
        }
      }
    }
  }

  return max(ans + int(euler.size()), 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:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int i = 0; i < A.size(); ++i){
      |                  ~~^~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 10068 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 0 ms 604 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 0 ms 604 KB Output is correct
25 Correct 2 ms 344 KB Output is correct
26 Correct 2 ms 1112 KB Output is correct
27 Correct 2 ms 1116 KB Output is correct
28 Correct 3 ms 1116 KB Output is correct
29 Correct 2 ms 1116 KB Output is correct
30 Correct 1 ms 860 KB Output is correct
31 Correct 3 ms 1068 KB Output is correct
32 Correct 2 ms 1116 KB Output is correct

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 348 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 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Incorrect 1 ms 348 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 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 0 ms 604 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Incorrect 1 ms 348 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 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 0 ms 604 KB Output is correct
26 Correct 2 ms 344 KB Output is correct
27 Correct 2 ms 1112 KB Output is correct
28 Correct 2 ms 1116 KB Output is correct
29 Correct 3 ms 1116 KB Output is correct
30 Correct 2 ms 1116 KB Output is correct
31 Correct 1 ms 860 KB Output is correct
32 Correct 3 ms 1068 KB Output is correct
33 Correct 2 ms 1116 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Incorrect 1 ms 348 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 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 0 ms 604 KB Output is correct
26 Correct 2 ms 344 KB Output is correct
27 Correct 2 ms 1112 KB Output is correct
28 Correct 2 ms 1116 KB Output is correct
29 Correct 3 ms 1116 KB Output is correct
30 Correct 2 ms 1116 KB Output is correct
31 Correct 1 ms 860 KB Output is correct
32 Correct 3 ms 1068 KB Output is correct
33 Correct 2 ms 1116 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
37 Halted 0 ms 0 KB -