oj.uz

Submission #939897

# Submission time Handle Problem Language Result Execution time Memory
939897 2024-03-06T23:17:16 Z AdamGS Closing Time (IOI23_closing) C++17
63 / 100
 147 ms 48556 KB 
#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=2e5+7;
vector<pair<ll,ll>>V[LIM];
ll odl[LIM][2], czy[LIM], ile[LIM], n;
void DFS(int x, int o, int k) {
  for(auto i : V[x]) if(i.st!=o) {
    odl[i.st][k]=odl[x][k]+i.nd;
    DFS(i.st, x, k);
  }
}
void DFS2(int x, int o) {
  for(auto i : V[x]) if(i.st!=o) {
    DFS2(i.st, x);
    if(czy[i.st]) czy[x]=1;
  }
}
int max_score(int _N, int x, int y, ll k, vector<int>_U, vector<int>_V, vector<int>_W) {
  n=_N;
  rep(i, n) {
    V[i].clear();
    odl[i][0]=odl[i][1]=czy[i]=ile[i]=0;
  }
  rep(i, n-1) {
    V[_U[i]].pb({_V[i], _W[i]});
    V[_V[i]].pb({_U[i], _W[i]});
  }
  DFS(x, x, 0);
  DFS(y, y, 1);
  vector<ll>P;
  ll sum1=0, sum2=0;
  int ans1=0, ans2=0;
  rep(i, n) {
    if(odl[i][0]>odl[i][1]) swap(odl[i][0], odl[i][1]);
    odl[i][1]-=odl[i][0];
    P.pb(odl[i][0]);
  }
  sort(all(P));
  for(auto i : P) if(sum1+i<=k) {
    sum1+=i;
    ++ans1;
  }
  czy[y]=1;
  DFS2(x, x);
  vector<pair<pair<ll,ll>,ll>>S;
  rep(i, n) {
    if(czy[i]) {
      sum2+=odl[i][0];
      ile[i]=1;
      ++ans2;
      S.pb({{2*odl[i][1], 1}, i});
    } else if(odl[i][0]>=odl[i][1]) S.pb({{odl[i][0]+odl[i][1], 2}, i});
    else {
      S.pb({{2*odl[i][0], 1}, i});
      S.pb({{2*odl[i][1], 1}, i});
    }
  }
  if(sum2>k) return ans1;
  sort(all(S));
  for(auto i : S) if(sum2+i.st.st*i.st.nd/2<=k) {
    sum2+=i.st.st*i.st.nd/2;
    ans2+=i.st.nd;
    ile[i.nd]+=i.st.nd;
  }
  if(ans1>ans2) return ans1;
  rep(i, n) {
    if(ile[i]==0) {
      if(sum2+odl[i][0]<=k) return ans2+1;
    } else if(ile[i]==1) {
      if(sum2+odl[i][1]<=k) return ans2+1;
    }
  }
  ll dwa=INF;
  rep(i, n) if(ile[i]==0) dwa=min(dwa, odl[i][0]+odl[i][1]);
  rep(i, n) if(ile[i]==2 && sum2-odl[i][1]+dwa<=k) return ans2+1;
  rep(i, n) if(ile[i]==1 && sum2-odl[i][0]+dwa<=k) return ans2+1;
  return ans2;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 48400 KB Output is correct
2 Correct 147 ms 48556 KB Output is correct
3 Correct 63 ms 13904 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11096 KB Output is correct
2 Correct 2 ms 11352 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 2 ms 11100 KB Output is correct
6 Correct 2 ms 11192 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 11228 KB Output is correct
10 Correct 3 ms 11100 KB Output is correct
11 Correct 2 ms 11260 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11096 KB Output is correct
2 Correct 2 ms 11352 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 2 ms 11100 KB Output is correct
6 Correct 2 ms 11192 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 11228 KB Output is correct
10 Correct 3 ms 11100 KB Output is correct
11 Correct 2 ms 11260 KB Output is correct
12 Correct 2 ms 11100 KB Output is correct
13 Correct 3 ms 11100 KB Output is correct
14 Correct 2 ms 11100 KB Output is correct
15 Correct 3 ms 11100 KB Output is correct
16 Correct 2 ms 11100 KB Output is correct
17 Correct 3 ms 11100 KB Output is correct
18 Correct 2 ms 11200 KB Output is correct
19 Correct 2 ms 11100 KB Output is correct
20 Correct 2 ms 11100 KB Output is correct
21 Correct 2 ms 11100 KB Output is correct
22 Correct 2 ms 11100 KB Output is correct
23 Correct 2 ms 11100 KB Output is correct
24 Correct 3 ms 11192 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11096 KB Output is correct
2 Correct 2 ms 11352 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 2 ms 11100 KB Output is correct
6 Correct 2 ms 11192 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 11228 KB Output is correct
10 Correct 3 ms 11100 KB Output is correct
11 Correct 2 ms 11260 KB Output is correct
12 Correct 2 ms 11100 KB Output is correct
13 Correct 3 ms 11100 KB Output is correct
14 Correct 2 ms 11100 KB Output is correct
15 Correct 3 ms 11100 KB Output is correct
16 Correct 2 ms 11100 KB Output is correct
17 Correct 3 ms 11100 KB Output is correct
18 Correct 2 ms 11200 KB Output is correct
19 Correct 2 ms 11100 KB Output is correct
20 Correct 2 ms 11100 KB Output is correct
21 Correct 2 ms 11100 KB Output is correct
22 Correct 2 ms 11100 KB Output is correct
23 Correct 2 ms 11100 KB Output is correct
24 Correct 3 ms 11192 KB Output is correct
25 Correct 4 ms 11096 KB Output is correct
26 Correct 3 ms 12120 KB Output is correct
27 Correct 3 ms 11612 KB Output is correct
28 Correct 4 ms 11868 KB Output is correct
29 Correct 3 ms 11816 KB Output is correct
30 Correct 3 ms 11612 KB Output is correct
31 Correct 4 ms 11820 KB Output is correct
32 Correct 4 ms 11868 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 3 ms 11096 KB Output is correct
3 Correct 2 ms 11352 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 2 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 3 ms 11096 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 2 ms 11100 KB Output is correct
13 Correct 2 ms 11196 KB Output is correct
14 Correct 2 ms 11348 KB Output is correct
15 Correct 2 ms 11100 KB Output is correct
16 Correct 2 ms 11100 KB Output is correct
17 Correct 2 ms 11096 KB Output is correct
18 Correct 2 ms 11100 KB Output is correct
19 Correct 2 ms 11200 KB Output is correct
20 Correct 2 ms 11100 KB Output is correct
21 Correct 2 ms 11100 KB Output is correct
22 Correct 3 ms 11232 KB Output is correct
23 Correct 2 ms 11096 KB Output is correct
24 Correct 2 ms 11100 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 3 ms 11096 KB Output is correct
3 Correct 2 ms 11352 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 2 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11192 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 2 ms 11228 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 2 ms 11260 KB Output is correct
13 Correct 2 ms 11100 KB Output is correct
14 Correct 3 ms 11100 KB Output is correct
15 Correct 2 ms 11100 KB Output is correct
16 Correct 3 ms 11100 KB Output is correct
17 Correct 2 ms 11100 KB Output is correct
18 Correct 3 ms 11100 KB Output is correct
19 Correct 2 ms 11100 KB Output is correct
20 Correct 2 ms 11100 KB Output is correct
21 Correct 2 ms 11100 KB Output is correct
22 Correct 3 ms 11096 KB Output is correct
23 Correct 3 ms 11100 KB Output is correct
24 Correct 2 ms 11100 KB Output is correct
25 Correct 2 ms 11196 KB Output is correct
26 Correct 2 ms 11348 KB Output is correct
27 Correct 2 ms 11100 KB Output is correct
28 Correct 2 ms 11100 KB Output is correct
29 Correct 2 ms 11096 KB Output is correct
30 Correct 2 ms 11100 KB Output is correct
31 Correct 2 ms 11200 KB Output is correct
32 Correct 2 ms 11100 KB Output is correct
33 Correct 2 ms 11100 KB Output is correct
34 Correct 3 ms 11232 KB Output is correct
35 Correct 2 ms 11096 KB Output is correct
36 Correct 2 ms 11100 KB Output is correct
37 Correct 2 ms 11096 KB Output is correct
38 Correct 2 ms 11100 KB Output is correct
39 Correct 2 ms 11100 KB Output is correct
40 Correct 2 ms 11100 KB Output is correct
41 Correct 2 ms 11100 KB Output is correct
42 Correct 2 ms 11100 KB Output is correct
43 Correct 2 ms 11100 KB Output is correct
44 Correct 2 ms 11100 KB Output is correct
45 Correct 2 ms 11100 KB Output is correct
46 Correct 2 ms 11096 KB Output is correct
47 Correct 2 ms 11100 KB Output is correct
48 Correct 3 ms 11096 KB Output is correct
49 Correct 2 ms 11100 KB Output is correct
50 Correct 2 ms 11100 KB Output is correct

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 3 ms 11096 KB Output is correct
3 Correct 2 ms 11352 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 2 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11192 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 2 ms 11228 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 2 ms 11260 KB Output is correct
13 Correct 2 ms 11100 KB Output is correct
14 Correct 3 ms 11100 KB Output is correct
15 Correct 2 ms 11100 KB Output is correct
16 Correct 3 ms 11100 KB Output is correct
17 Correct 2 ms 11100 KB Output is correct
18 Correct 3 ms 11100 KB Output is correct
19 Correct 2 ms 11200 KB Output is correct
20 Correct 2 ms 11100 KB Output is correct
21 Correct 2 ms 11100 KB Output is correct
22 Correct 2 ms 11100 KB Output is correct
23 Correct 2 ms 11100 KB Output is correct
24 Correct 2 ms 11100 KB Output is correct
25 Correct 3 ms 11192 KB Output is correct
26 Correct 2 ms 11100 KB Output is correct
27 Correct 2 ms 11100 KB Output is correct
28 Correct 2 ms 11100 KB Output is correct
29 Correct 3 ms 11096 KB Output is correct
30 Correct 3 ms 11100 KB Output is correct
31 Correct 2 ms 11100 KB Output is correct
32 Correct 2 ms 11196 KB Output is correct
33 Correct 2 ms 11348 KB Output is correct
34 Correct 2 ms 11100 KB Output is correct
35 Correct 2 ms 11100 KB Output is correct
36 Correct 2 ms 11096 KB Output is correct
37 Correct 2 ms 11100 KB Output is correct
38 Correct 2 ms 11200 KB Output is correct
39 Correct 2 ms 11100 KB Output is correct
40 Correct 2 ms 11100 KB Output is correct
41 Correct 3 ms 11232 KB Output is correct
42 Correct 2 ms 11096 KB Output is correct
43 Correct 2 ms 11100 KB Output is correct
44 Correct 2 ms 11096 KB Output is correct
45 Correct 2 ms 11100 KB Output is correct
46 Correct 2 ms 11100 KB Output is correct
47 Correct 2 ms 11100 KB Output is correct
48 Correct 2 ms 11100 KB Output is correct
49 Correct 2 ms 11100 KB Output is correct
50 Correct 2 ms 11100 KB Output is correct
51 Correct 2 ms 11100 KB Output is correct
52 Correct 2 ms 11100 KB Output is correct
53 Correct 2 ms 11096 KB Output is correct
54 Correct 2 ms 11100 KB Output is correct
55 Correct 3 ms 11096 KB Output is correct
56 Correct 2 ms 11100 KB Output is correct
57 Correct 2 ms 11100 KB Output is correct
58 Correct 2 ms 11100 KB Output is correct
59 Correct 2 ms 11100 KB Output is correct
60 Correct 3 ms 11100 KB Output is correct
61 Correct 3 ms 11100 KB Output is correct
62 Correct 2 ms 11100 KB Output is correct
63 Correct 2 ms 11100 KB Output is correct
64 Correct 3 ms 11100 KB Output is correct
65 Incorrect 2 ms 11100 KB 1st lines differ - on the 1st token, expected: '164', found: '165'
66 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 3 ms 11096 KB Output is correct
3 Correct 2 ms 11352 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 2 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11192 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 2 ms 11228 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 2 ms 11260 KB Output is correct
13 Correct 2 ms 11100 KB Output is correct
14 Correct 3 ms 11100 KB Output is correct
15 Correct 2 ms 11100 KB Output is correct
16 Correct 3 ms 11100 KB Output is correct
17 Correct 2 ms 11100 KB Output is correct
18 Correct 3 ms 11100 KB Output is correct
19 Correct 2 ms 11200 KB Output is correct
20 Correct 2 ms 11100 KB Output is correct
21 Correct 2 ms 11100 KB Output is correct
22 Correct 2 ms 11100 KB Output is correct
23 Correct 2 ms 11100 KB Output is correct
24 Correct 2 ms 11100 KB Output is correct
25 Correct 3 ms 11192 KB Output is correct
26 Correct 4 ms 11096 KB Output is correct
27 Correct 3 ms 12120 KB Output is correct
28 Correct 3 ms 11612 KB Output is correct
29 Correct 4 ms 11868 KB Output is correct
30 Correct 3 ms 11816 KB Output is correct
31 Correct 3 ms 11612 KB Output is correct
32 Correct 4 ms 11820 KB Output is correct
33 Correct 4 ms 11868 KB Output is correct
34 Correct 2 ms 11100 KB Output is correct
35 Correct 2 ms 11100 KB Output is correct
36 Correct 2 ms 11100 KB Output is correct
37 Correct 3 ms 11096 KB Output is correct
38 Correct 3 ms 11100 KB Output is correct
39 Correct 2 ms 11100 KB Output is correct
40 Correct 2 ms 11196 KB Output is correct
41 Correct 2 ms 11348 KB Output is correct
42 Correct 2 ms 11100 KB Output is correct
43 Correct 2 ms 11100 KB Output is correct
44 Correct 2 ms 11096 KB Output is correct
45 Correct 2 ms 11100 KB Output is correct
46 Correct 2 ms 11200 KB Output is correct
47 Correct 2 ms 11100 KB Output is correct
48 Correct 2 ms 11100 KB Output is correct
49 Correct 3 ms 11232 KB Output is correct
50 Correct 2 ms 11096 KB Output is correct
51 Correct 2 ms 11100 KB Output is correct
52 Correct 2 ms 11096 KB Output is correct
53 Correct 2 ms 11100 KB Output is correct
54 Correct 2 ms 11100 KB Output is correct
55 Correct 2 ms 11100 KB Output is correct
56 Correct 2 ms 11100 KB Output is correct
57 Correct 2 ms 11100 KB Output is correct
58 Correct 2 ms 11100 KB Output is correct
59 Correct 2 ms 11100 KB Output is correct
60 Correct 2 ms 11100 KB Output is correct
61 Correct 2 ms 11096 KB Output is correct
62 Correct 2 ms 11100 KB Output is correct
63 Correct 3 ms 11096 KB Output is correct
64 Correct 2 ms 11100 KB Output is correct
65 Correct 2 ms 11100 KB Output is correct
66 Correct 2 ms 11100 KB Output is correct
67 Correct 2 ms 11100 KB Output is correct
68 Correct 3 ms 11100 KB Output is correct
69 Correct 3 ms 11100 KB Output is correct
70 Correct 2 ms 11100 KB Output is correct
71 Correct 2 ms 11100 KB Output is correct
72 Correct 3 ms 11100 KB Output is correct
73 Incorrect 2 ms 11100 KB 1st lines differ - on the 1st token, expected: '164', found: '165'
74 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 3 ms 11096 KB Output is correct
3 Correct 2 ms 11352 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 2 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11192 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 2 ms 11228 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 2 ms 11260 KB Output is correct
13 Correct 2 ms 11100 KB Output is correct
14 Correct 3 ms 11100 KB Output is correct
15 Correct 2 ms 11100 KB Output is correct
16 Correct 3 ms 11100 KB Output is correct
17 Correct 2 ms 11100 KB Output is correct
18 Correct 3 ms 11100 KB Output is correct
19 Correct 2 ms 11200 KB Output is correct
20 Correct 2 ms 11100 KB Output is correct
21 Correct 2 ms 11100 KB Output is correct
22 Correct 2 ms 11100 KB Output is correct
23 Correct 2 ms 11100 KB Output is correct
24 Correct 2 ms 11100 KB Output is correct
25 Correct 3 ms 11192 KB Output is correct
26 Correct 4 ms 11096 KB Output is correct
27 Correct 3 ms 12120 KB Output is correct
28 Correct 3 ms 11612 KB Output is correct
29 Correct 4 ms 11868 KB Output is correct
30 Correct 3 ms 11816 KB Output is correct
31 Correct 3 ms 11612 KB Output is correct
32 Correct 4 ms 11820 KB Output is correct
33 Correct 4 ms 11868 KB Output is correct
34 Correct 2 ms 11100 KB Output is correct
35 Correct 2 ms 11100 KB Output is correct
36 Correct 2 ms 11100 KB Output is correct
37 Correct 3 ms 11096 KB Output is correct
38 Correct 3 ms 11100 KB Output is correct
39 Correct 2 ms 11100 KB Output is correct
40 Correct 2 ms 11196 KB Output is correct
41 Correct 2 ms 11348 KB Output is correct
42 Correct 2 ms 11100 KB Output is correct
43 Correct 2 ms 11100 KB Output is correct
44 Correct 2 ms 11096 KB Output is correct
45 Correct 2 ms 11100 KB Output is correct
46 Correct 2 ms 11200 KB Output is correct
47 Correct 2 ms 11100 KB Output is correct
48 Correct 2 ms 11100 KB Output is correct
49 Correct 3 ms 11232 KB Output is correct
50 Correct 2 ms 11096 KB Output is correct
51 Correct 2 ms 11100 KB Output is correct
52 Correct 2 ms 11096 KB Output is correct
53 Correct 2 ms 11100 KB Output is correct
54 Correct 2 ms 11100 KB Output is correct
55 Correct 2 ms 11100 KB Output is correct
56 Correct 2 ms 11100 KB Output is correct
57 Correct 2 ms 11100 KB Output is correct
58 Correct 2 ms 11100 KB Output is correct
59 Correct 2 ms 11100 KB Output is correct
60 Correct 2 ms 11100 KB Output is correct
61 Correct 2 ms 11096 KB Output is correct
62 Correct 2 ms 11100 KB Output is correct
63 Correct 3 ms 11096 KB Output is correct
64 Correct 2 ms 11100 KB Output is correct
65 Correct 2 ms 11100 KB Output is correct
66 Correct 2 ms 11100 KB Output is correct
67 Correct 2 ms 11100 KB Output is correct
68 Correct 3 ms 11100 KB Output is correct
69 Correct 3 ms 11100 KB Output is correct
70 Correct 2 ms 11100 KB Output is correct
71 Correct 2 ms 11100 KB Output is correct
72 Correct 3 ms 11100 KB Output is correct
73 Incorrect 2 ms 11100 KB 1st lines differ - on the 1st token, expected: '164', found: '165'
74 Halted 0 ms 0 KB -