oj.uz

Submission #955533

# Submission time Handle Problem Language Result Execution time Memory
955533 2024-03-30T21:33:46 Z ZeroCool Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 46852 KB 
#include "closing.h"
#include <bits/stdc++.h>
using ll = long long;

#define pb push_back
#define all(v) v.begin(), v.end()

const ll N = 3e5 + 10;
const ll INF = 1e15;

using namespace std;



ll n, s1, s2, k;

vector<pair<ll,ll> > g[N];

ll dist[N][2];

void dfs1(ll x,ll p,ll t){
    for(auto [u, w] : g[x]){
        if(u == p)continue;
        dist[u][t] = dist[x][t] + w;
        dfs1(u, x, t);
    }
}

ll C[2][N];

bool path[N];

vector<ll> curr;
void dfs2(ll x,ll p){
    curr.pb(x);
    if(x == s2){
        for(auto v : curr){
            path[v] = true;
        }
        return;
    }

    for(auto [u, w] : g[x]){
        if(u == p)continue;
        dfs2(u, x);
    }
    curr.pop_back();
}

int max_score(int _n, int _x, int _y, long long _k,vector<int> u, vector<int> v, vector<int> w){
    n = _n;
    s1 = _x;
    s2 = _y;
    k = _k;
    memset(path, 0, sizeof path);
    memset(dist, 0, sizeof dist);
    memset(C, 0, sizeof C);
    for(int i = 0;i<n;i++)g[i].clear();
    for(ll i = 0;i<u.size();i++){
        g[u[i]].pb({v[i], w[i]});
        g[v[i]].pb({u[i], w[i]});
    }
    curr.clear();
    dfs1(s1, -1, 0);
    //assert(0);
    dfs1(s2, -1, 1);

    for(ll i = 0;i<n;i++){
        C[0][i] = min(dist[i][0], dist[i][1]);
        C[1][i] = max(dist[i][0], dist[i][1]);
       // cout<<i<<": "<<C[0][i]<<" "<<C[1][i]<<endl;
    }

    vector<ll> vc;
    for(ll i = 0;i<n;i++)vc.pb(C[0][i]);

    sort(all(vc));
    ll sum = 0;
    ll cnt = 0;
    for(auto u : vc){
        sum += u;
        if(sum > k)break;
        cnt++;
    }
    ll ans = cnt;
    //return cnt;
    vector<ll> dp[2];
    dp[0].resize(2 * n + 5, INF);
    dfs2(s1, -1);
    dp[0][0] = 0;
    
    for(ll i = 0;i<n;i++){
    //    assert(0);
       // cout<<path[i]<<" ";
        dp[1].resize(2 * n + 5, INF);

        for(ll j = 0;j<=2 * n;j++){
            if(!path[i])dp[1][j] = min(dp[1][j], dp[0][j]);

            dp[1][j+1] = min(dp[1][j+1], dp[0][j] + C[0][i]);
            dp[1][j+2] = min(dp[1][j+2], dp[0][j] + C[1][i]);

        }
        swap(dp[0], dp[1]);
       
    }
    cout<<endl;
  //  assert(0);
    for(ll i = ans+1;i<dp[0].size();i++){
       // cout<<dp[0][i]<<endl;
        if(dp[0][i] <= k)ans = i;
    }
    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:59:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(ll i = 0;i<u.size();i++){
      |                  ~^~~~~~~~~
closing.cpp:109:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(ll i = ans+1;i<dp[0].size();i++){
      |                      ~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 46852 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 17080 KB Output is correct
7 Correct 3 ms 16984 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 4 ms 16988 KB Output is correct
12 Correct 3 ms 17184 KB Output is correct
13 Correct 3 ms 16988 KB Output is correct
14 Incorrect 4 ms 16988 KB 1st lines differ - on the 1st token, expected: '38', found: '42'
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 17080 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Incorrect 4 ms 16988 KB 1st lines differ - on the 1st token, expected: '44', found: '57'
12 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 17080 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Incorrect 4 ms 16988 KB 1st lines differ - on the 1st token, expected: '44', found: '57'
12 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 17080 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Incorrect 4 ms 16988 KB 1st lines differ - on the 1st token, expected: '44', found: '57'
12 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 17080 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Incorrect 4 ms 16988 KB 1st lines differ - on the 1st token, expected: '44', found: '57'
12 Halted 0 ms 0 KB -