oj.uz

Submission #1074942

# Submission time Handle Problem Language Result Execution time Memory
1074942 2024-08-25T16:58:03 Z bleahbleah Closing Time (IOI23_closing) C++17
43 / 100
 181 ms 47148 KB 
#include "closing.h"

#include <vector>
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
#define int ll

#define sz(x) ((int)(x).size())

using pii = pair<int,int>;

const int nmax = 2e5 + 5;

ll dx[nmax], dy[nmax];
int p[nmax];
vector<pii> g[nmax];

void filld(int node, int f, ll *d) {
   p[node] = f;
   for(auto [x, c] : g[node]) {
      if(x == f) continue;
      d[x] = d[node] + c;
      filld(x, node, d);
   }
   return;
}

int separate(int N, ll S) {
   vector<pii> s;
   for(int i = 0; i < N; i++) {
      s.emplace_back(i, 1);
      s.emplace_back(i, 2);
   }
   sort(all(s), [&](auto a, auto b) {
      return (a.second == 1? dx[a.first] : dy[a.first]) < (b.second == 1? dx[b.first] : dy[b.first]);
   });
   
   vector<int> occ(N, 0);
   int cnt = 0;
   for(auto [x, t] : s) {
      if(occ[x]) continue;
      auto C = (t == 1? dx[x] : dy[x]);
      if(S < C) break;
      S -= C;
      occ[x] = 1;
      cnt++;
   }
   
   return cnt;
}



signed max_score(signed N, signed X, signed Y, long long S, std::vector<signed> U, std::vector<signed> V, std::vector<signed> W) {
   for(int i = 0; i <= N; i++) g[i].clear();
   
   for(int i = 0; i < sz(U); i++) {
      g[U[i]].emplace_back(V[i], W[i]);
      g[V[i]].emplace_back(U[i], W[i]);
   }
   
   dx[X] = dy[Y] = 0;
   filld(X, X, dx);
   filld(Y, Y, dy);
   
   const int opt1 = separate(N, S);
   //cerr << opt1 << '\n';
   
   vector<int> onchain(N, 0);
   int t = X;
   while(t != Y) {
      onchain[t] = 1;
      t = p[t];
   }
   onchain[Y] = 1;
   
   vector<pair<ll, ll>> s;
   
   int opt2 = 0;
   for(int node = 0; node < N; node++) {
      //cerr << onchain[node] << ' ';
      if(onchain[node]) {
         int a = dx[node], b = dy[node];
         if(a > b) swap(a, b);
         S -= a;
         s.emplace_back(b - a, -1);
         opt2++;
      }
      else {
         int a = dx[node], b = dy[node];
         if(a > b) swap(a, b);
         b -= a;
         if(a <= b) {
            s.emplace_back(a, -1);
            s.emplace_back(b, -1);
         }
         else {
            s.emplace_back(a, b);
         }
      }
   }
   //cerr << '\n' << S << '\n';
   
   if(S < 0) return opt1;
   sort(all(s), [&](auto a, auto b) {
      auto C = (a.second == -1? 2 * a.first : a.first + a.second);
      auto D = (b.second == -1? 2 * b.first : b.first + b.second);
      return C < D;
   });
   
   //for(auto [a, b] : s) cerr << a << ' ' << b << '\n';
   
   auto simulate = [&s](int start, int S) {
      int cnt = 0;     
     for(int it = start; it <= sz(s); it++) {
         auto [a, b] = s[it];
         if(b == -1) {
            if(a > S) break;
            S -= a;
            cnt++;
         }
         else {
            if(a + b > S) {
               for(int j = it + 1; j < sz(s); j++) 
                  a = min(a, s[j].first);
               if(S < a) break;
               cnt++;
               break;
            }
            else {
               S -= a + b;
               cnt += 2;
            }
         } 
      }
      return cnt;
   };
   
   vector<int> oper1;
   vector<pii> oper2;
   
   for(int it = 0; it < sz(s); it++) {
      auto [a, b] = s[it];
      if(b == -1) {
         if(a > S) break;
         S -= a;
         opt2++;
         oper1.emplace_back(a);
      }
      else {
         if(a + b > S) {
            int mx = simulate(it, S);
            if(sz(oper1)) {
               mx = max(simulate(it, S + oper1.back()) - 1, mx);
            }
            if(sz(oper2)) {
               auto [yi, er] = oper2.back();
               mx = max(simulate(it, S + er) - 1, mx);
               mx = max(simulate(it, S + yi + er) - 2, mx);
            }
            if(sz(oper1) && sz(oper2)) {
               auto [yi, er] = oper2.back();
               mx = max(simulate(it, S + yi + er + oper1.back()) - 3, mx);
            }
            opt2 += mx;
            break;
         }
         else {
            S -= a + b;
            oper2.emplace_back(a, b);
            opt2 += 2;
         }
      }
   }
   
   return max(opt1, opt2);
}

#undef int

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 46868 KB Output is correct
2 Correct 181 ms 47148 KB Output is correct
3 Correct 80 ms 10376 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4940 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 5208 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 3 ms 4956 KB Output is correct
17 Correct 2 ms 4956 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 3 ms 5100 KB Output is correct
20 Correct 3 ms 5212 KB Output is correct
21 Correct 3 ms 5212 KB Output is correct
22 Correct 2 ms 5148 KB Output is correct
23 Correct 3 ms 5144 KB Output is correct
24 Correct 3 ms 5208 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4940 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 5208 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 3 ms 4956 KB Output is correct
17 Correct 2 ms 4956 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 3 ms 5100 KB Output is correct
20 Correct 3 ms 5212 KB Output is correct
21 Correct 3 ms 5212 KB Output is correct
22 Correct 2 ms 5148 KB Output is correct
23 Correct 3 ms 5144 KB Output is correct
24 Correct 3 ms 5208 KB Output is correct
25 Correct 3 ms 5212 KB Output is correct
26 Correct 3 ms 5724 KB Output is correct
27 Correct 5 ms 5724 KB Output is correct
28 Correct 3 ms 5724 KB Output is correct
29 Correct 4 ms 5724 KB Output is correct
30 Correct 3 ms 5628 KB Output is correct
31 Correct 3 ms 5724 KB Output is correct
32 Correct 4 ms 5724 KB Output is correct

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4952 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 5144 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 4956 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4952 KB Output is correct
17 Correct 2 ms 4956 KB Output is correct
18 Correct 2 ms 5208 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Correct 2 ms 5148 KB Output is correct
21 Correct 2 ms 4956 KB Output is correct
22 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '39', found: '41'
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4952 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4940 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 4956 KB Output is correct
13 Correct 2 ms 5208 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 3 ms 4956 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Correct 2 ms 4956 KB Output is correct
21 Correct 2 ms 5144 KB Output is correct
22 Correct 2 ms 4956 KB Output is correct
23 Correct 2 ms 4956 KB Output is correct
24 Correct 2 ms 4956 KB Output is correct
25 Correct 2 ms 4956 KB Output is correct
26 Correct 2 ms 4956 KB Output is correct
27 Correct 2 ms 4956 KB Output is correct
28 Correct 2 ms 4952 KB Output is correct
29 Correct 2 ms 4956 KB Output is correct
30 Correct 2 ms 5208 KB Output is correct
31 Correct 2 ms 4956 KB Output is correct
32 Correct 2 ms 5148 KB Output is correct
33 Correct 2 ms 4956 KB Output is correct
34 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '39', found: '41'
35 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4952 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4940 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 4956 KB Output is correct
13 Correct 2 ms 5208 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 3 ms 4956 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Correct 3 ms 5100 KB Output is correct
21 Correct 3 ms 5212 KB Output is correct
22 Correct 3 ms 5212 KB Output is correct
23 Correct 2 ms 5148 KB Output is correct
24 Correct 3 ms 5144 KB Output is correct
25 Correct 3 ms 5208 KB Output is correct
26 Correct 2 ms 4956 KB Output is correct
27 Correct 2 ms 4956 KB Output is correct
28 Correct 2 ms 5144 KB Output is correct
29 Correct 2 ms 4956 KB Output is correct
30 Correct 2 ms 4956 KB Output is correct
31 Correct 2 ms 4956 KB Output is correct
32 Correct 2 ms 4956 KB Output is correct
33 Correct 2 ms 4956 KB Output is correct
34 Correct 2 ms 4956 KB Output is correct
35 Correct 2 ms 4952 KB Output is correct
36 Correct 2 ms 4956 KB Output is correct
37 Correct 2 ms 5208 KB Output is correct
38 Correct 2 ms 4956 KB Output is correct
39 Correct 2 ms 5148 KB Output is correct
40 Correct 2 ms 4956 KB Output is correct
41 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '39', found: '41'
42 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4952 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4940 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 4956 KB Output is correct
13 Correct 2 ms 5208 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 3 ms 4956 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Correct 3 ms 5100 KB Output is correct
21 Correct 3 ms 5212 KB Output is correct
22 Correct 3 ms 5212 KB Output is correct
23 Correct 2 ms 5148 KB Output is correct
24 Correct 3 ms 5144 KB Output is correct
25 Correct 3 ms 5208 KB Output is correct
26 Correct 3 ms 5212 KB Output is correct
27 Correct 3 ms 5724 KB Output is correct
28 Correct 5 ms 5724 KB Output is correct
29 Correct 3 ms 5724 KB Output is correct
30 Correct 4 ms 5724 KB Output is correct
31 Correct 3 ms 5628 KB Output is correct
32 Correct 3 ms 5724 KB Output is correct
33 Correct 4 ms 5724 KB Output is correct
34 Correct 2 ms 4956 KB Output is correct
35 Correct 2 ms 4956 KB Output is correct
36 Correct 2 ms 5144 KB Output is correct
37 Correct 2 ms 4956 KB Output is correct
38 Correct 2 ms 4956 KB Output is correct
39 Correct 2 ms 4956 KB Output is correct
40 Correct 2 ms 4956 KB Output is correct
41 Correct 2 ms 4956 KB Output is correct
42 Correct 2 ms 4956 KB Output is correct
43 Correct 2 ms 4952 KB Output is correct
44 Correct 2 ms 4956 KB Output is correct
45 Correct 2 ms 5208 KB Output is correct
46 Correct 2 ms 4956 KB Output is correct
47 Correct 2 ms 5148 KB Output is correct
48 Correct 2 ms 4956 KB Output is correct
49 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '39', found: '41'
50 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4952 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4940 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 4956 KB Output is correct
13 Correct 2 ms 5208 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 3 ms 4956 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Correct 3 ms 5100 KB Output is correct
21 Correct 3 ms 5212 KB Output is correct
22 Correct 3 ms 5212 KB Output is correct
23 Correct 2 ms 5148 KB Output is correct
24 Correct 3 ms 5144 KB Output is correct
25 Correct 3 ms 5208 KB Output is correct
26 Correct 3 ms 5212 KB Output is correct
27 Correct 3 ms 5724 KB Output is correct
28 Correct 5 ms 5724 KB Output is correct
29 Correct 3 ms 5724 KB Output is correct
30 Correct 4 ms 5724 KB Output is correct
31 Correct 3 ms 5628 KB Output is correct
32 Correct 3 ms 5724 KB Output is correct
33 Correct 4 ms 5724 KB Output is correct
34 Correct 2 ms 4956 KB Output is correct
35 Correct 2 ms 4956 KB Output is correct
36 Correct 2 ms 5144 KB Output is correct
37 Correct 2 ms 4956 KB Output is correct
38 Correct 2 ms 4956 KB Output is correct
39 Correct 2 ms 4956 KB Output is correct
40 Correct 2 ms 4956 KB Output is correct
41 Correct 2 ms 4956 KB Output is correct
42 Correct 2 ms 4956 KB Output is correct
43 Correct 2 ms 4952 KB Output is correct
44 Correct 2 ms 4956 KB Output is correct
45 Correct 2 ms 5208 KB Output is correct
46 Correct 2 ms 4956 KB Output is correct
47 Correct 2 ms 5148 KB Output is correct
48 Correct 2 ms 4956 KB Output is correct
49 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '39', found: '41'
50 Halted 0 ms 0 KB -