oj.uz

Submission #1080787

# Submission time Handle Problem Language Result Execution time Memory
1080787 2024-08-29T14:20:48 Z ALeonidou Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 348 KB 
#include "shortcut.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define F first
#define S second
#define pb push_back
#define sz(x) (ll)x.size()

typedef vector <ll> vi;
typedef pair<ll,ll> ii;
typedef vector <ii> vii;

#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;

void printVct(vi &v){
    for (ll i =0; i<sz(v); i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}
 
#define INF 1000000000000000000

vector <vii> adj;
priority_queue <ii, vii, greater<ii> > pq;
ii dijkstra(ll s){      //O(nlogn)
    vi dis(sz(adj), INF);
    dis[s] = 0;
    pq.push(ii(0, s));
    while (!pq.empty()){
        ii f = pq.top();
        pq.pop();  
        ll c = f.S, w = f.F;
        if (w > dis[c]) continue;
        for (ll i =0; i<sz(adj[c]); i++){
            ii v = adj[c][i];
            if (v.S + dis[c] < dis[v.F]){
                dis[v.F] = v.S + dis[c];
                pq.push(ii(dis[v.F], v.F));
            }
        }
    }
    ll maxi = 0, maxiIdx = s;
    for (ll i =0; i<sz(dis); i++){
        if (maxi < dis[i]){
            maxi = dis[i];
            maxiIdx = i;
        }
    }
    return ii(maxiIdx, maxi);
}

ll solve(){     //O(n^2 * logn)
    ll maxi = 0;
    for (ll i =0; i<sz(adj); i++){
        maxi = max(maxi, dijkstra(i).S);
    }
    return maxi;
}

ll find_shortcut(int N, vector<int> l, vector<int> d, int C)
{
    ll c = C;
    ll n = N;
    ll m = n;
    for (ll i =0; i<sz(d); i++){
        if (d[i]) m++;
    }
    adj.assign(m, vii());
    for (ll i =0; i<sz(l)-1; i++){
        adj[i].pb(ii(i+1, l[i]));
        adj[i+1].pb(ii(i, l[i]));
    }
    ll tmp_cnt = 0;
    for (ll i =0; i<sz(d); i++){
        if (!d[i]) continue;
        adj[i].pb(ii(tmp_cnt+n, d[i]));
        adj[tmp_cnt+n].pb(ii(i, d[i]));
        tmp_cnt++;
    }

    ll ans = INF;
    for (ll i =0; i<n; i++){    //O(n^4 * logn)
        for (ll j = i+1; j<n; j++){
            // dbg2(i,j);
            cout.flush();
            adj[i].pb(ii(j,c));
            adj[j].pb(ii(i,c));
            ans = min(ans, solve());
            adj[i].pop_back();
            adj[j].pop_back();
        }
    }
    
    return ans;
}

/*
4 10
10 20 20
0 40 0 30

20 30
10 10 10 20 10 30 10 10 5 10 10 10 20 10 30 10 10 5 5
20 10 30 20 10 40 20 40 30 20 20 10 30 20 10 40 20 40 30 20

*/

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n = 4, 80 is a correct answer
2 Incorrect 0 ms 348 KB n = 9, incorrect answer: jury 110 vs contestant 130
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n = 4, 80 is a correct answer
2 Incorrect 0 ms 348 KB n = 9, incorrect answer: jury 110 vs contestant 130
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n = 4, 80 is a correct answer
2 Incorrect 0 ms 348 KB n = 9, incorrect answer: jury 110 vs contestant 130
3 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n = 4, 80 is a correct answer
2 Incorrect 0 ms 348 KB n = 9, incorrect answer: jury 110 vs contestant 130
3 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n = 4, 80 is a correct answer
2 Incorrect 0 ms 348 KB n = 9, incorrect answer: jury 110 vs contestant 130
3 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n = 4, 80 is a correct answer
2 Incorrect 0 ms 348 KB n = 9, incorrect answer: jury 110 vs contestant 130
3 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n = 4, 80 is a correct answer
2 Incorrect 0 ms 348 KB n = 9, incorrect answer: jury 110 vs contestant 130
3 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n = 4, 80 is a correct answer
2 Incorrect 0 ms 348 KB n = 9, incorrect answer: jury 110 vs contestant 130
3 Halted 0 ms 0 KB -