Submission #1045989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045989		AIF_is_carving	Closing Time (IOI23_closing)	C++17	8 / 100	102 ms	30548 KiB

closing

#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
• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17