oj.uz

Submission #1045989

# Submission time Handle Problem Language Result Execution time Memory
1045989 2024-08-06T08:50:41 Z AIF_is_carving Closing Time (IOI23_closing) C++17
8 / 100
 102 ms 30548 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(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});
                s.insert({{lenghtX[u.first], u.first}, 1});
            }
        }
        else{
            visy[v] = true;
            for(auto u: graph[v]){
                // 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});
                s.insert({{lenghtY[u.first], u.first}, 2});
            }
        }

        // 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 2 ms 4956 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 26952 KB Output is correct
2 Correct 102 ms 30548 KB Output is correct
3 Correct 33 ms 7512 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Incorrect 2 ms 4952 KB 1st lines differ - on the 1st token, expected: '30', found: '28'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Incorrect 2 ms 4952 KB 1st lines differ - on the 1st token, expected: '30', found: '28'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Incorrect 2 ms 4952 KB 1st lines differ - on the 1st token, expected: '30', found: '28'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Incorrect 2 ms 4952 KB 1st lines differ - on the 1st token, expected: '30', found: '28'
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Incorrect 2 ms 4952 KB 1st lines differ - on the 1st token, expected: '30', found: '28'
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Incorrect 2 ms 4952 KB 1st lines differ - on the 1st token, expected: '30', found: '28'
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Incorrect 2 ms 4952 KB 1st lines differ - on the 1st token, expected: '30', found: '28'
4 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Incorrect 2 ms 4952 KB 1st lines differ - on the 1st token, expected: '30', found: '28'
4 Halted 0 ms 0 KB -