oj.uz

Submission #841773

# Submission time Handle Problem Language Result Execution time Memory
841773 2023-09-02T05:00:23 Z Lyestria Closing Time (IOI23_closing) C++17
35 / 100
 93 ms 40688 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;
}

int 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]});
    }
    fpath(x,x,y);
    reverse(all(path));
    for(int a : path)inpath[a]=1;
    ll D = dis[y];
    struct Choice {
        ll d;
        int a;
        bool sec;
        bool operator<(const Choice &o) const {return d>o.d;}
    };
    vector<ll> costt;
    priority_queue<Choice> pq;
    for(auto [a,w] : g[x]) if(!inpath[a]) {
        pq.push({w,a,0});
    }
    for(auto [a,w] : g[y]) if(!inpath[a]) {
        pq.push({w,a,0});
    }

    while(pq.size()) {
        auto [d,a,sec] = pq.top();
        pq.pop();
        vis[a]=1;
        costt.push_back(d);
        if(sec)continue;
        pq.push({D,a,1});
        for(auto [b,w] : g[a])if(!inpath[b]&&!vis[b]){
            pq.push({d+w,b,0});
        }
    }

    vector<ll> costl;

    pq.push({0,x,0});
    pq.push({0,y,0});
    while(pq.size()) {
        auto [d,a,s] = pq.top();
        pq.pop();
        if(vis[a])continue;
        vis[a]=1;
        costl.push_back(d);
        for(auto [b,w] : g[a]) if(inpath[b]&&!vis[b]){
            pq.push({d+w,b,0});
        } 
    }
    // cerr << costl.size() << endl;
    vector<ll> cost2;
    for(int a : path) {
        cost2.push_back(abs(dis[a]-(D-dis[a])));
    }
    sort(all(cost2));
    for(ll x : cost2) costl.push_back(x);

    int ans = 0;
    ll sum = 0;
    for(int i=0;i<costl.size();i++)sum+=costl[i];
    // cerr << costl.size() << " " << costt.size() << endl;
    for(int i=-1,j=(int)costl.size()-1;i<(int)costt.size();i++){
        while(sum>k&&j>=0){
            sum-=costl[j];
            j--;
            // cerr << sum << j << endl;
        }
        // cerr << "ij " << i << " " << j << endl; 
        if(sum<=k)ans=max(ans,(i+1)+(j+1));
        if(i==(int)costt.size()-1)break;
        sum+=costt[i+1];
    }
    return ans;
}

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:55: 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++){
      |                 ~^~~~~~~~~
closing.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i=0;i<costl.size();i++)sum+=costl[i];
      |                 ~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 40688 KB 1st lines differ - on the 1st token, expected: '451', found: '264'
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16220 KB Output is correct
2 Correct 3 ms 16220 KB Output is correct
3 Correct 4 ms 16220 KB Output is correct
4 Correct 3 ms 16328 KB Output is correct
5 Correct 4 ms 16216 KB Output is correct
6 Correct 3 ms 16220 KB Output is correct
7 Correct 4 ms 16220 KB Output is correct
8 Correct 3 ms 16220 KB Output is correct
9 Correct 3 ms 16220 KB Output is correct
10 Correct 3 ms 16220 KB Output is correct
11 Correct 3 ms 16220 KB Output is correct
12 Correct 3 ms 16220 KB Output is correct
13 Correct 3 ms 16220 KB Output is correct
14 Correct 3 ms 16220 KB Output is correct
15 Correct 4 ms 16220 KB Output is correct
16 Correct 3 ms 16216 KB Output is correct
17 Correct 4 ms 16316 KB Output is correct
18 Correct 3 ms 16220 KB Output is correct
19 Correct 3 ms 16324 KB Output is correct
20 Correct 4 ms 16216 KB Output is correct
21 Correct 4 ms 16220 KB Output is correct
22 Correct 3 ms 16220 KB Output is correct
23 Correct 3 ms 16220 KB Output is correct
24 Correct 3 ms 16220 KB Output is correct
25 Correct 4 ms 16220 KB Output is correct
26 Correct 5 ms 16732 KB Output is correct
27 Correct 5 ms 16740 KB Output is correct
28 Correct 4 ms 16732 KB Output is correct
29 Correct 5 ms 16732 KB Output is correct
30 Correct 4 ms 16476 KB Output is correct
31 Correct 6 ms 16772 KB Output is correct
32 Correct 4 ms 16732 KB Output is correct

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16220 KB Output is correct
2 Correct 4 ms 16220 KB Output is correct
3 Correct 3 ms 16220 KB Output is correct
4 Correct 4 ms 16220 KB Output is correct
5 Correct 3 ms 16328 KB Output is correct
6 Correct 4 ms 16216 KB Output is correct
7 Incorrect 3 ms 16220 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 3 ms 16220 KB Output is correct
2 Correct 4 ms 16220 KB Output is correct
3 Correct 3 ms 16220 KB Output is correct
4 Correct 4 ms 16220 KB Output is correct
5 Correct 3 ms 16328 KB Output is correct
6 Correct 4 ms 16216 KB Output is correct
7 Correct 3 ms 16220 KB Output is correct
8 Correct 4 ms 16220 KB Output is correct
9 Correct 3 ms 16220 KB Output is correct
10 Correct 3 ms 16220 KB Output is correct
11 Correct 3 ms 16220 KB Output is correct
12 Correct 3 ms 16220 KB Output is correct
13 Correct 3 ms 16220 KB Output is correct
14 Correct 3 ms 16220 KB Output is correct
15 Correct 3 ms 16220 KB Output is correct
16 Correct 4 ms 16220 KB Output is correct
17 Correct 3 ms 16216 KB Output is correct
18 Correct 4 ms 16316 KB Output is correct
19 Incorrect 3 ms 16220 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 3 ms 16220 KB Output is correct
2 Correct 4 ms 16220 KB Output is correct
3 Correct 3 ms 16220 KB Output is correct
4 Correct 4 ms 16220 KB Output is correct
5 Correct 3 ms 16328 KB Output is correct
6 Correct 4 ms 16216 KB Output is correct
7 Correct 3 ms 16220 KB Output is correct
8 Correct 4 ms 16220 KB Output is correct
9 Correct 3 ms 16220 KB Output is correct
10 Correct 3 ms 16220 KB Output is correct
11 Correct 3 ms 16220 KB Output is correct
12 Correct 3 ms 16220 KB Output is correct
13 Correct 3 ms 16220 KB Output is correct
14 Correct 3 ms 16220 KB Output is correct
15 Correct 3 ms 16220 KB Output is correct
16 Correct 4 ms 16220 KB Output is correct
17 Correct 3 ms 16216 KB Output is correct
18 Correct 4 ms 16316 KB Output is correct
19 Correct 3 ms 16220 KB Output is correct
20 Correct 3 ms 16324 KB Output is correct
21 Correct 4 ms 16216 KB Output is correct
22 Correct 4 ms 16220 KB Output is correct
23 Correct 3 ms 16220 KB Output is correct
24 Correct 3 ms 16220 KB Output is correct
25 Correct 3 ms 16220 KB Output is correct
26 Incorrect 3 ms 16220 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 3 ms 16220 KB Output is correct
2 Correct 4 ms 16220 KB Output is correct
3 Correct 3 ms 16220 KB Output is correct
4 Correct 4 ms 16220 KB Output is correct
5 Correct 3 ms 16328 KB Output is correct
6 Correct 4 ms 16216 KB Output is correct
7 Correct 3 ms 16220 KB Output is correct
8 Correct 4 ms 16220 KB Output is correct
9 Correct 3 ms 16220 KB Output is correct
10 Correct 3 ms 16220 KB Output is correct
11 Correct 3 ms 16220 KB Output is correct
12 Correct 3 ms 16220 KB Output is correct
13 Correct 3 ms 16220 KB Output is correct
14 Correct 3 ms 16220 KB Output is correct
15 Correct 3 ms 16220 KB Output is correct
16 Correct 4 ms 16220 KB Output is correct
17 Correct 3 ms 16216 KB Output is correct
18 Correct 4 ms 16316 KB Output is correct
19 Correct 3 ms 16220 KB Output is correct
20 Correct 3 ms 16324 KB Output is correct
21 Correct 4 ms 16216 KB Output is correct
22 Correct 4 ms 16220 KB Output is correct
23 Correct 3 ms 16220 KB Output is correct
24 Correct 3 ms 16220 KB Output is correct
25 Correct 3 ms 16220 KB Output is correct
26 Correct 4 ms 16220 KB Output is correct
27 Correct 5 ms 16732 KB Output is correct
28 Correct 5 ms 16740 KB Output is correct
29 Correct 4 ms 16732 KB Output is correct
30 Correct 5 ms 16732 KB Output is correct
31 Correct 4 ms 16476 KB Output is correct
32 Correct 6 ms 16772 KB Output is correct
33 Correct 4 ms 16732 KB Output is correct
34 Incorrect 3 ms 16220 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 3 ms 16220 KB Output is correct
2 Correct 4 ms 16220 KB Output is correct
3 Correct 3 ms 16220 KB Output is correct
4 Correct 4 ms 16220 KB Output is correct
5 Correct 3 ms 16328 KB Output is correct
6 Correct 4 ms 16216 KB Output is correct
7 Correct 3 ms 16220 KB Output is correct
8 Correct 4 ms 16220 KB Output is correct
9 Correct 3 ms 16220 KB Output is correct
10 Correct 3 ms 16220 KB Output is correct
11 Correct 3 ms 16220 KB Output is correct
12 Correct 3 ms 16220 KB Output is correct
13 Correct 3 ms 16220 KB Output is correct
14 Correct 3 ms 16220 KB Output is correct
15 Correct 3 ms 16220 KB Output is correct
16 Correct 4 ms 16220 KB Output is correct
17 Correct 3 ms 16216 KB Output is correct
18 Correct 4 ms 16316 KB Output is correct
19 Correct 3 ms 16220 KB Output is correct
20 Correct 3 ms 16324 KB Output is correct
21 Correct 4 ms 16216 KB Output is correct
22 Correct 4 ms 16220 KB Output is correct
23 Correct 3 ms 16220 KB Output is correct
24 Correct 3 ms 16220 KB Output is correct
25 Correct 3 ms 16220 KB Output is correct
26 Correct 4 ms 16220 KB Output is correct
27 Correct 5 ms 16732 KB Output is correct
28 Correct 5 ms 16740 KB Output is correct
29 Correct 4 ms 16732 KB Output is correct
30 Correct 5 ms 16732 KB Output is correct
31 Correct 4 ms 16476 KB Output is correct
32 Correct 6 ms 16772 KB Output is correct
33 Correct 4 ms 16732 KB Output is correct
34 Incorrect 3 ms 16220 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
35 Halted 0 ms 0 KB -