oj.uz

Submission #1045940

# Submission time Handle Problem Language Result Execution time Memory
1045940 2024-08-06T08:38:31 Z AIF_is_carving Closing Time (IOI23_closing) C++17
43 / 100
 103 ms 32596 KB 
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;

const int N = 2e5+5;
vector<pair<int, ll>> graph[N];
bool visx[N];
ll lenghtX[N];
bool visy[N];
ll lenghtY[N];

void dfsX(int node){
    visx[node] = true;
    for(auto child: graph[node]){
        if(!visx[child.first]){
            lenghtX[child.first] =  1LL*child.second + 1LL*lenghtX[node];
            dfsX(child.first);
        }
    }
    return;
}

void dfsY(int node){
    visy[node] = true;
    for(auto child: graph[node]){
        if(!visy[child.first]){
            lenghtY[child.first] =  1LL*child.second + 1LL*lenghtY[node];
            dfsY(child.first);
        }
    }
    return;
}

int max_score(int n, int x, int y, ll k, std::vector<int> u,
              std::vector<int> v, std::vector<int> w){
    for(int i = 0; i<n-1; i++){
        graph[u[i]].push_back({v[i], 1LL*w[i]});
        graph[v[i]].push_back({u[i], 1LL*w[i]});
    }

    dfsX(x);
    dfsY(y);

    for(int i = 0; i<=n; i++){
        visx[i] = 0;
        visy[i] = 0;
    }
    
    multiset<pair<pair<ll, ll>, ll>> s;
    s.insert({{0, x}, 1});
    s.insert({{0, y}, 2});
 
    ll sum = 0;
    int cnt = 0;
    while(s.size()>0){
        auto it = s.begin();
        int v = (*it).first.second;
        ll wt = (*it).first.first;
        int mark = (*it).second;
        s.erase(it);
        if(mark == 1 && visx[v] == 1) continue;
        else if(mark == 2 && visy[v] == 1) continue;

        sum+= wt;
        //cout<<sum<<" "<<v<<" "<<wt<<"\n";
        if(sum<= k) cnt+=1;
        else break;
        
        if(s.find({{lenghtX[v]+ lenghtY[v] - wt, v}, 3-mark}) != s.end()){
            s.erase({{lenghtX[v]+ lenghtY[v] - wt, v}, 3-mark});
            s.insert({{lenghtX[v]+ lenghtY[v] - 2*wt, v}, 3-mark});
        }
        
        if(mark == 1){
            //if(visx[v]) continue;
            visx[v] = true;
            for(auto u: graph[v]){
                //if(visx[u.first] == 0){
                    if(visy[u.first]) s.insert({{max(lenghtX[u.first], lenghtY[u.first]) - lenghtY[u.first], u.first}, 1});
                    else s.insert({{lenghtX[u.first], u.first}, 1});

                    //visx[u.first] = true;
                //}
            }
        }
        else{
            //if(visy[v]) continue;
            visy[v] = true;
            for(auto u: graph[v]){
                //if(visy[u.first] == 0){
                    if(visx[u.first]) s.insert({{max(lenghtX[u.first], lenghtY[u.first]) - lenghtX[u.first], u.first}, 2});
                    else s.insert({{lenghtY[u.first], u.first}, 2});

                    //visy[u.first] = true;
                //}
            }
        }

        // for(auto x: s){
        //     cout<<x.first.first<<" "<<x.first.second<<" "<<x.second<<"\n";
        // }
        // cout<<"\n";

    }
 

    for(int i = 0; i<=n; i++){
        lenghtX[i] = 0;
        lenghtY[i] = 0;
        visx[i] = 0;
        visy[i] = 0;
        graph[i].clear();
    }

    return cnt;

}

// int main() {
//   int Q;
//   assert(1 == scanf("%d", &Q));

//   std::vector<int> N(Q), X(Q), Y(Q);
//   std::vector<long long> K(Q);
//   std::vector<std::vector<int>> U(Q), V(Q), W(Q);

//   for (int q = 0; q < Q; q++) {
//     assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));

//     U[q].resize(N[q] - 1);
//     V[q].resize(N[q] - 1);
//     W[q].resize(N[q] - 1);
//     for (int i = 0; i < N[q] - 1; ++i) {
//       assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
//     }
//   }
//   fclose(stdin);

//   std::vector<int> result(Q);
//   for (int q = 0; q < Q; q++) {
//     result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
//   }

//   for (int q = 0; q < Q; q++) {
//     printf("%d\n", result[q]);
//   }
//   fclose(stdout);

//   return 0;
// }

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 28880 KB Output is correct
2 Correct 65 ms 32596 KB Output is correct
3 Correct 33 ms 10320 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6232 KB Output is correct
2 Correct 1 ms 6236 KB Output is correct
3 Correct 1 ms 6236 KB Output is correct
4 Correct 1 ms 6248 KB Output is correct
5 Correct 1 ms 6236 KB Output is correct
6 Correct 1 ms 6236 KB Output is correct
7 Correct 1 ms 6236 KB Output is correct
8 Correct 1 ms 6236 KB Output is correct
9 Correct 2 ms 6236 KB Output is correct
10 Correct 1 ms 6236 KB Output is correct
11 Correct 2 ms 6236 KB Output is correct
12 Correct 1 ms 6320 KB Output is correct
13 Correct 2 ms 6232 KB Output is correct
14 Correct 1 ms 6344 KB Output is correct
15 Correct 2 ms 6236 KB Output is correct
16 Correct 1 ms 6236 KB Output is correct
17 Correct 2 ms 6232 KB Output is correct
18 Correct 2 ms 6232 KB Output is correct
19 Correct 2 ms 6440 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 2 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6232 KB Output is correct
2 Correct 1 ms 6236 KB Output is correct
3 Correct 1 ms 6236 KB Output is correct
4 Correct 1 ms 6248 KB Output is correct
5 Correct 1 ms 6236 KB Output is correct
6 Correct 1 ms 6236 KB Output is correct
7 Correct 1 ms 6236 KB Output is correct
8 Correct 1 ms 6236 KB Output is correct
9 Correct 2 ms 6236 KB Output is correct
10 Correct 1 ms 6236 KB Output is correct
11 Correct 2 ms 6236 KB Output is correct
12 Correct 1 ms 6320 KB Output is correct
13 Correct 2 ms 6232 KB Output is correct
14 Correct 1 ms 6344 KB Output is correct
15 Correct 2 ms 6236 KB Output is correct
16 Correct 1 ms 6236 KB Output is correct
17 Correct 2 ms 6232 KB Output is correct
18 Correct 2 ms 6232 KB Output is correct
19 Correct 2 ms 6440 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 2 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 3 ms 6492 KB Output is correct
26 Correct 2 ms 6700 KB Output is correct
27 Correct 2 ms 6748 KB Output is correct
28 Correct 2 ms 6748 KB Output is correct
29 Correct 2 ms 6748 KB Output is correct
30 Correct 2 ms 6748 KB Output is correct
31 Correct 2 ms 6748 KB Output is correct
32 Correct 3 ms 6748 KB Output is correct

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6232 KB Output is correct
2 Correct 1 ms 6232 KB Output is correct
3 Correct 1 ms 6236 KB Output is correct
4 Correct 1 ms 6236 KB Output is correct
5 Correct 1 ms 6248 KB Output is correct
6 Correct 1 ms 6236 KB Output is correct
7 Incorrect 2 ms 6236 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6232 KB Output is correct
2 Correct 1 ms 6232 KB Output is correct
3 Correct 1 ms 6236 KB Output is correct
4 Correct 1 ms 6236 KB Output is correct
5 Correct 1 ms 6248 KB Output is correct
6 Correct 1 ms 6236 KB Output is correct
7 Correct 1 ms 6236 KB Output is correct
8 Correct 1 ms 6236 KB Output is correct
9 Correct 1 ms 6236 KB Output is correct
10 Correct 2 ms 6236 KB Output is correct
11 Correct 1 ms 6236 KB Output is correct
12 Correct 2 ms 6236 KB Output is correct
13 Correct 1 ms 6320 KB Output is correct
14 Correct 2 ms 6232 KB Output is correct
15 Correct 1 ms 6344 KB Output is correct
16 Correct 2 ms 6236 KB Output is correct
17 Correct 1 ms 6236 KB Output is correct
18 Correct 2 ms 6232 KB Output is correct
19 Incorrect 2 ms 6236 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
20 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6232 KB Output is correct
2 Correct 1 ms 6232 KB Output is correct
3 Correct 1 ms 6236 KB Output is correct
4 Correct 1 ms 6236 KB Output is correct
5 Correct 1 ms 6248 KB Output is correct
6 Correct 1 ms 6236 KB Output is correct
7 Correct 1 ms 6236 KB Output is correct
8 Correct 1 ms 6236 KB Output is correct
9 Correct 1 ms 6236 KB Output is correct
10 Correct 2 ms 6236 KB Output is correct
11 Correct 1 ms 6236 KB Output is correct
12 Correct 2 ms 6236 KB Output is correct
13 Correct 1 ms 6320 KB Output is correct
14 Correct 2 ms 6232 KB Output is correct
15 Correct 1 ms 6344 KB Output is correct
16 Correct 2 ms 6236 KB Output is correct
17 Correct 1 ms 6236 KB Output is correct
18 Correct 2 ms 6232 KB Output is correct
19 Correct 2 ms 6232 KB Output is correct
20 Correct 2 ms 6440 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 2 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Incorrect 2 ms 6236 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
27 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6232 KB Output is correct
2 Correct 1 ms 6232 KB Output is correct
3 Correct 1 ms 6236 KB Output is correct
4 Correct 1 ms 6236 KB Output is correct
5 Correct 1 ms 6248 KB Output is correct
6 Correct 1 ms 6236 KB Output is correct
7 Correct 1 ms 6236 KB Output is correct
8 Correct 1 ms 6236 KB Output is correct
9 Correct 1 ms 6236 KB Output is correct
10 Correct 2 ms 6236 KB Output is correct
11 Correct 1 ms 6236 KB Output is correct
12 Correct 2 ms 6236 KB Output is correct
13 Correct 1 ms 6320 KB Output is correct
14 Correct 2 ms 6232 KB Output is correct
15 Correct 1 ms 6344 KB Output is correct
16 Correct 2 ms 6236 KB Output is correct
17 Correct 1 ms 6236 KB Output is correct
18 Correct 2 ms 6232 KB Output is correct
19 Correct 2 ms 6232 KB Output is correct
20 Correct 2 ms 6440 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 2 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 3 ms 6492 KB Output is correct
27 Correct 2 ms 6700 KB Output is correct
28 Correct 2 ms 6748 KB Output is correct
29 Correct 2 ms 6748 KB Output is correct
30 Correct 2 ms 6748 KB Output is correct
31 Correct 2 ms 6748 KB Output is correct
32 Correct 2 ms 6748 KB Output is correct
33 Correct 3 ms 6748 KB Output is correct
34 Incorrect 2 ms 6236 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
35 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6232 KB Output is correct
2 Correct 1 ms 6232 KB Output is correct
3 Correct 1 ms 6236 KB Output is correct
4 Correct 1 ms 6236 KB Output is correct
5 Correct 1 ms 6248 KB Output is correct
6 Correct 1 ms 6236 KB Output is correct
7 Correct 1 ms 6236 KB Output is correct
8 Correct 1 ms 6236 KB Output is correct
9 Correct 1 ms 6236 KB Output is correct
10 Correct 2 ms 6236 KB Output is correct
11 Correct 1 ms 6236 KB Output is correct
12 Correct 2 ms 6236 KB Output is correct
13 Correct 1 ms 6320 KB Output is correct
14 Correct 2 ms 6232 KB Output is correct
15 Correct 1 ms 6344 KB Output is correct
16 Correct 2 ms 6236 KB Output is correct
17 Correct 1 ms 6236 KB Output is correct
18 Correct 2 ms 6232 KB Output is correct
19 Correct 2 ms 6232 KB Output is correct
20 Correct 2 ms 6440 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 2 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 3 ms 6492 KB Output is correct
27 Correct 2 ms 6700 KB Output is correct
28 Correct 2 ms 6748 KB Output is correct
29 Correct 2 ms 6748 KB Output is correct
30 Correct 2 ms 6748 KB Output is correct
31 Correct 2 ms 6748 KB Output is correct
32 Correct 2 ms 6748 KB Output is correct
33 Correct 3 ms 6748 KB Output is correct
34 Incorrect 2 ms 6236 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
35 Halted 0 ms 0 KB -