oj.uz

Submission #1045986

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

const int N = 2e4+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;

}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 10844 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Incorrect 0 ms 860 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 1 ms 860 KB Output is correct
2 Incorrect 0 ms 860 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 1 ms 860 KB Output is correct
2 Incorrect 0 ms 860 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 0 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Incorrect 0 ms 860 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 0 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Incorrect 0 ms 860 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 0 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Incorrect 0 ms 860 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 0 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Incorrect 0 ms 860 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 0 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Incorrect 0 ms 860 KB 1st lines differ - on the 1st token, expected: '30', found: '28'
4 Halted 0 ms 0 KB -