oj.uz

Submission #843113

# Submission time Handle Problem Language Result Execution time Memory
843113 2023-09-03T17:15:33 Z Lyestria Closing Time (IOI23_closing) C++17
43 / 100
 107 ms 40420 KB 
#include "closing.h"

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()

using vi = vector<int>;
using ll = long long;

const int maxn = 5e5 + 10;
const ll inf = 1e18 + 100;

vector<pair<int,ll>> g[maxn];
vector<int> path;
bool inpath[maxn];
ll dis[maxn];
bool fpath(int x,int p,int t) {
    if(x==t){
        path.push_back(x);
        return true;
    }
    for(auto [y,w] : g[x]) if(y!=p) {
        dis[y] = dis[x] + w;
        if(fpath(y,x,t)){
            path.push_back(x);
            return true;
        }
    }
    return false;
}

bool vis[maxn];
int max_score(int n, int x, int y, long long k,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    // cerr << endl;
    for(int i=0;i<n;i++) g[i].clear(),inpath[i]=vis[i]=dis[i]=0;
    path.clear();
    for(int i=0;i<U.size();i++){
        g[U[i]].push_back({V[i],W[i]});
        g[V[i]].push_back({U[i],W[i]});
    }

    // no overlap
    int ans1 = [&](){
        priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
        pq.push({0,x});
        pq.push({0,y});
        ll sum = 0;
        int ans = 0;
        while(pq.size()){
            auto [d,a] = pq.top();
            pq.pop();
            // cerr << ans << " " << sum << " " << k << " " << d << " " << vis[a] << endl;
            if(vis[a])continue;
            vis[a]=1;
            if(sum+d>k){
                return ans;
            }
            sum+=d;
            ans++;
            // cerr << ans << endl;
            for(auto [b,w] : g[a]) {
                pq.push({d+w,b});
            }
        }
        return ans;
    }();

    // overlap (start with path)
    int ans2 = [&](){
        for(int i=0;i<n;i++)vis[i]=0;
        fpath(x,x,y);
        reverse(all(path));
        for(int a : path)inpath[a]=1;
        int ans = 0;
        ll sum = 0;
        const ll D = dis[y];

        for(int a : path) {
            ans++;
            sum += min(dis[a],D-dis[a]);
        }
        if(sum > k) return 0;

        struct State {
            ll c1, c2;
            int a;
            ll eval() const {return min(c1*2,c2); }
            bool operator<(const State &o) const {return eval() > o.eval(); }
        };

        priority_queue<State>pq;
        for(int a : path) {
            pq.push({max(dis[a],D-dis[a])-min(dis[a],D-dis[a]), inf, a});
            for(auto [b,w] : g[a]) if(!inpath[b]) {
                pq.push({min(dis[a],D-dis[a])+w, max(dis[a],D-dis[a])+w, b});
            }
            vis[a]=1;
        }

        while(pq.size()){
            auto [c1,c2,a] = pq.top();
            pq.pop();
            vis[a]=1;
            if(sum+c1<=k){
                ans++;
                sum+=c1;
            }
            else continue;
            if(c2==inf)continue;
            pq.push({c2-c1,inf,a});
            for(auto [b,w] : g[a]) if(!vis[b]) {
                pq.push({c1+w,c2+w,b});
            }
        }

        return ans;
    }();

    return max(ans1,ans2);
}

Compilation message

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:37:62: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   37 |     for(int i=0;i<n;i++) g[i].clear(),inpath[i]=vis[i]=dis[i]=0;
      |                                                        ~~~~~~^~
closing.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0;i<U.size();i++){
      |                 ~^~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 34996 KB Output is correct
2 Correct 107 ms 40420 KB Output is correct
3 Correct 47 ms 17432 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 4 ms 14936 KB Output is correct
3 Correct 4 ms 14680 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14680 KB Output is correct
7 Correct 4 ms 14684 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 4 ms 14936 KB Output is correct
11 Correct 3 ms 14680 KB Output is correct
12 Correct 4 ms 14784 KB Output is correct
13 Correct 4 ms 14684 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 2 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 3 ms 14684 KB Output is correct
20 Correct 3 ms 14784 KB Output is correct
21 Correct 3 ms 14684 KB Output is correct
22 Correct 3 ms 14684 KB Output is correct
23 Correct 3 ms 14684 KB Output is correct
24 Correct 3 ms 14684 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 4 ms 14936 KB Output is correct
3 Correct 4 ms 14680 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14680 KB Output is correct
7 Correct 4 ms 14684 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 4 ms 14936 KB Output is correct
11 Correct 3 ms 14680 KB Output is correct
12 Correct 4 ms 14784 KB Output is correct
13 Correct 4 ms 14684 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 2 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 3 ms 14684 KB Output is correct
20 Correct 3 ms 14784 KB Output is correct
21 Correct 3 ms 14684 KB Output is correct
22 Correct 3 ms 14684 KB Output is correct
23 Correct 3 ms 14684 KB Output is correct
24 Correct 3 ms 14684 KB Output is correct
25 Correct 4 ms 14684 KB Output is correct
26 Correct 5 ms 14940 KB Output is correct
27 Correct 5 ms 14940 KB Output is correct
28 Correct 5 ms 15192 KB Output is correct
29 Correct 5 ms 15196 KB Output is correct
30 Correct 4 ms 14940 KB Output is correct
31 Correct 5 ms 15032 KB Output is correct
32 Correct 4 ms 15448 KB Output is correct

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14680 KB Output is correct
2 Correct 3 ms 14680 KB Output is correct
3 Correct 4 ms 14936 KB Output is correct
4 Correct 4 ms 14680 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14680 KB Output is correct
8 Correct 4 ms 14684 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 4 ms 14936 KB Output is correct
12 Correct 3 ms 14680 KB Output is correct
13 Correct 4 ms 14784 KB Output is correct
14 Correct 4 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 2 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 3 ms 14684 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Correct 3 ms 14784 KB Output is correct
22 Correct 3 ms 14684 KB Output is correct
23 Correct 3 ms 14684 KB Output is correct
24 Correct 3 ms 14684 KB Output is correct
25 Correct 3 ms 14684 KB Output is correct
26 Correct 3 ms 14680 KB Output is correct
27 Correct 3 ms 14684 KB Output is correct
28 Incorrect 3 ms 14940 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
29 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14680 KB Output is correct
2 Correct 3 ms 14680 KB Output is correct
3 Correct 4 ms 14936 KB Output is correct
4 Correct 4 ms 14680 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14680 KB Output is correct
8 Correct 4 ms 14684 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 4 ms 14936 KB Output is correct
12 Correct 3 ms 14680 KB Output is correct
13 Correct 4 ms 14784 KB Output is correct
14 Correct 4 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 2 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 3 ms 14684 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Correct 3 ms 14784 KB Output is correct
22 Correct 3 ms 14684 KB Output is correct
23 Correct 3 ms 14684 KB Output is correct
24 Correct 3 ms 14684 KB Output is correct
25 Correct 3 ms 14684 KB Output is correct
26 Correct 4 ms 14684 KB Output is correct
27 Correct 5 ms 14940 KB Output is correct
28 Correct 5 ms 14940 KB Output is correct
29 Correct 5 ms 15192 KB Output is correct
30 Correct 5 ms 15196 KB Output is correct
31 Correct 4 ms 14940 KB Output is correct
32 Correct 5 ms 15032 KB Output is correct
33 Correct 4 ms 15448 KB Output is correct
34 Correct 3 ms 14680 KB Output is correct
35 Correct 3 ms 14684 KB Output is correct
36 Incorrect 3 ms 14940 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
37 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14680 KB Output is correct
2 Correct 3 ms 14680 KB Output is correct
3 Correct 4 ms 14936 KB Output is correct
4 Correct 4 ms 14680 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14680 KB Output is correct
8 Correct 4 ms 14684 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 4 ms 14936 KB Output is correct
12 Correct 3 ms 14680 KB Output is correct
13 Correct 4 ms 14784 KB Output is correct
14 Correct 4 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 2 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 3 ms 14684 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Correct 3 ms 14784 KB Output is correct
22 Correct 3 ms 14684 KB Output is correct
23 Correct 3 ms 14684 KB Output is correct
24 Correct 3 ms 14684 KB Output is correct
25 Correct 3 ms 14684 KB Output is correct
26 Correct 4 ms 14684 KB Output is correct
27 Correct 5 ms 14940 KB Output is correct
28 Correct 5 ms 14940 KB Output is correct
29 Correct 5 ms 15192 KB Output is correct
30 Correct 5 ms 15196 KB Output is correct
31 Correct 4 ms 14940 KB Output is correct
32 Correct 5 ms 15032 KB Output is correct
33 Correct 4 ms 15448 KB Output is correct
34 Correct 3 ms 14680 KB Output is correct
35 Correct 3 ms 14684 KB Output is correct
36 Incorrect 3 ms 14940 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
37 Halted 0 ms 0 KB -