oj.uz

Submission #433369

# Submission time Handle Problem Language Result Execution time Memory
433369 2021-06-19T16:22:38 Z Monchito Shortcut (IOI16_shortcut) C++14
0 / 100
 21 ms 31820 KB 
#include "shortcut.h"
#include <queue>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
using ll = long long;

const int MAXN = 2e3;
const ll INF = 1e18;

int N;
vector<int> G[MAXN];
vector<ll> W[MAXN];
vector<vector<ll>> dist(MAXN, vector<ll>(MAXN));

ll dijkstra(int x) {
    priority_queue<pair<ll, int>> q;
    vector<ll> dist(N*2, INF);
    dist[x] = 0;
    q.push(make_pair(-0, x));
 
    while(!q.empty()) {
        pair<ll, int> p = q.top(); q.pop();
        int u = p.second;
 
        if(-p.first != dist[u]) continue;
 
        for(int i=0; i<(int)G[u].size(); i++) {
            int v = G[u][i];
            ll w = W[u][i];

            if(-p.first + w < dist[v]) {
                dist[v] = -p.first + w; 
                q.push(make_pair(-dist[v], v));
            }
        }
    }
 
    ll ret=0;
    for(int i=0; i<N*2; i++) {
        ret = max(ret, dist[i]); 
    }
 
    return ret;
}

pair<ll, int> BFS(int x) {
    vector<bool> vis(N*2, false);

    queue<pair<ll, int>> q;
    ll d = -INF; int r = -1;

    q.push(make_pair(0, x));

    while(!q.empty()) {
        pair<ll, int> p = q.front(); q.pop();
        int u = p.second;
        vis[u] = true;

        if(p.first > d) { d = p.first; r = u; }

        for(int i=0; i<(int)G[u].size(); i++) {
            int v = G[u][i];
            ll w = W[u][i];
            if(vis[v] || w == 0) continue;

            q.push(make_pair(p.first + w, v));
        }
    }

    return make_pair(d, r);
}

ll calc_diameter() {
    ll ret = -INF;
    for(int i=0; i<N*2; i++) 
        ret = max(ret, dijkstra(i));
    
    return ret;
}

void create_link(int u, int v, ll w) {
    G[u].push_back(v);
    W[u].push_back(w);
    G[v].push_back(u);
    W[v].push_back(w);
}

ll calc(ll w) {
    ll diameter; 
    set<pair<int,int>> nodes;

    for(int i=0; i<N; i++) {
        int c = BFS(i).second;  
        pair<ll,int> p = BFS(c);

        diameter = p.first;
        int d = p.second;

        if(c >= N) c -= N;
        if(d >= N) d -= N;

        if(c > d) swap(c, d);

        nodes.insert(make_pair(c, d));
    }

    ll ret = INF;

    for(auto it : nodes) {
        for(int i=it.first; i<it.second; i++) {
            create_link(i, it.second, w);         
            ret = min(ret, calc_diameter());
            G[i].pop_back();
            G[it.second].pop_back();
            W[i].pop_back();
            W[it.second].pop_back();
        }
    }

    return min(ret, diameter);
}

ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
    N = n;

    for(int i=0; i<n-1; i++) 
        create_link(i, i+1, l[i]);

    for(int i=0; i<n; i++) 
        create_link(i, i+N, d[i]); 
    
    return calc(c);
}

Compilation message

shortcut.cpp: In function 'll calc(ll)':
shortcut.cpp:91:8: warning: 'diameter' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |     ll diameter;
      |        ^~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31692 KB n = 4, 80 is a correct answer
2 Correct 18 ms 31724 KB n = 9, 110 is a correct answer
3 Correct 19 ms 31820 KB n = 4, 21 is a correct answer
4 Correct 17 ms 31692 KB n = 3, 4 is a correct answer
5 Correct 17 ms 31712 KB n = 2, 62 is a correct answer
6 Correct 18 ms 31692 KB n = 2, 3 is a correct answer
7 Correct 18 ms 31764 KB n = 3, 29 is a correct answer
8 Correct 17 ms 31792 KB n = 2, 3 is a correct answer
9 Correct 18 ms 31696 KB n = 2, 3 is a correct answer
10 Correct 18 ms 31728 KB n = 2, 2000000001 is a correct answer
11 Correct 19 ms 31652 KB n = 2, 3000000000 is a correct answer
12 Correct 18 ms 31692 KB n = 3, 3000000000 is a correct answer
13 Correct 18 ms 31724 KB n = 3, 3000000000 is a correct answer
14 Correct 18 ms 31756 KB n = 4, 3000000001 is a correct answer
15 Correct 18 ms 31788 KB n = 4, 4000000000 is a correct answer
16 Correct 21 ms 31648 KB n = 5, 4000000000 is a correct answer
17 Correct 21 ms 31768 KB n = 10, 1000000343 is a correct answer
18 Correct 19 ms 31788 KB n = 10, 3189 is a correct answer
19 Correct 19 ms 31720 KB n = 10, 7000000000 is a correct answer
20 Correct 18 ms 31784 KB n = 5, 12 is a correct answer
21 Correct 18 ms 31756 KB n = 5, 25 is a correct answer
22 Correct 18 ms 31744 KB n = 2, 122 is a correct answer
23 Correct 18 ms 31692 KB n = 10, 117 is a correct answer
24 Incorrect 18 ms 31780 KB n = 10, incorrect answer: jury 336 vs contestant 367
25 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31692 KB n = 4, 80 is a correct answer
2 Correct 18 ms 31724 KB n = 9, 110 is a correct answer
3 Correct 19 ms 31820 KB n = 4, 21 is a correct answer
4 Correct 17 ms 31692 KB n = 3, 4 is a correct answer
5 Correct 17 ms 31712 KB n = 2, 62 is a correct answer
6 Correct 18 ms 31692 KB n = 2, 3 is a correct answer
7 Correct 18 ms 31764 KB n = 3, 29 is a correct answer
8 Correct 17 ms 31792 KB n = 2, 3 is a correct answer
9 Correct 18 ms 31696 KB n = 2, 3 is a correct answer
10 Correct 18 ms 31728 KB n = 2, 2000000001 is a correct answer
11 Correct 19 ms 31652 KB n = 2, 3000000000 is a correct answer
12 Correct 18 ms 31692 KB n = 3, 3000000000 is a correct answer
13 Correct 18 ms 31724 KB n = 3, 3000000000 is a correct answer
14 Correct 18 ms 31756 KB n = 4, 3000000001 is a correct answer
15 Correct 18 ms 31788 KB n = 4, 4000000000 is a correct answer
16 Correct 21 ms 31648 KB n = 5, 4000000000 is a correct answer
17 Correct 21 ms 31768 KB n = 10, 1000000343 is a correct answer
18 Correct 19 ms 31788 KB n = 10, 3189 is a correct answer
19 Correct 19 ms 31720 KB n = 10, 7000000000 is a correct answer
20 Correct 18 ms 31784 KB n = 5, 12 is a correct answer
21 Correct 18 ms 31756 KB n = 5, 25 is a correct answer
22 Correct 18 ms 31744 KB n = 2, 122 is a correct answer
23 Correct 18 ms 31692 KB n = 10, 117 is a correct answer
24 Incorrect 18 ms 31780 KB n = 10, incorrect answer: jury 336 vs contestant 367
25 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31692 KB n = 4, 80 is a correct answer
2 Correct 18 ms 31724 KB n = 9, 110 is a correct answer
3 Correct 19 ms 31820 KB n = 4, 21 is a correct answer
4 Correct 17 ms 31692 KB n = 3, 4 is a correct answer
5 Correct 17 ms 31712 KB n = 2, 62 is a correct answer
6 Correct 18 ms 31692 KB n = 2, 3 is a correct answer
7 Correct 18 ms 31764 KB n = 3, 29 is a correct answer
8 Correct 17 ms 31792 KB n = 2, 3 is a correct answer
9 Correct 18 ms 31696 KB n = 2, 3 is a correct answer
10 Correct 18 ms 31728 KB n = 2, 2000000001 is a correct answer
11 Correct 19 ms 31652 KB n = 2, 3000000000 is a correct answer
12 Correct 18 ms 31692 KB n = 3, 3000000000 is a correct answer
13 Correct 18 ms 31724 KB n = 3, 3000000000 is a correct answer
14 Correct 18 ms 31756 KB n = 4, 3000000001 is a correct answer
15 Correct 18 ms 31788 KB n = 4, 4000000000 is a correct answer
16 Correct 21 ms 31648 KB n = 5, 4000000000 is a correct answer
17 Correct 21 ms 31768 KB n = 10, 1000000343 is a correct answer
18 Correct 19 ms 31788 KB n = 10, 3189 is a correct answer
19 Correct 19 ms 31720 KB n = 10, 7000000000 is a correct answer
20 Correct 18 ms 31784 KB n = 5, 12 is a correct answer
21 Correct 18 ms 31756 KB n = 5, 25 is a correct answer
22 Correct 18 ms 31744 KB n = 2, 122 is a correct answer
23 Correct 18 ms 31692 KB n = 10, 117 is a correct answer
24 Incorrect 18 ms 31780 KB n = 10, incorrect answer: jury 336 vs contestant 367
25 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31692 KB n = 4, 80 is a correct answer
2 Correct 18 ms 31724 KB n = 9, 110 is a correct answer
3 Correct 19 ms 31820 KB n = 4, 21 is a correct answer
4 Correct 17 ms 31692 KB n = 3, 4 is a correct answer
5 Correct 17 ms 31712 KB n = 2, 62 is a correct answer
6 Correct 18 ms 31692 KB n = 2, 3 is a correct answer
7 Correct 18 ms 31764 KB n = 3, 29 is a correct answer
8 Correct 17 ms 31792 KB n = 2, 3 is a correct answer
9 Correct 18 ms 31696 KB n = 2, 3 is a correct answer
10 Correct 18 ms 31728 KB n = 2, 2000000001 is a correct answer
11 Correct 19 ms 31652 KB n = 2, 3000000000 is a correct answer
12 Correct 18 ms 31692 KB n = 3, 3000000000 is a correct answer
13 Correct 18 ms 31724 KB n = 3, 3000000000 is a correct answer
14 Correct 18 ms 31756 KB n = 4, 3000000001 is a correct answer
15 Correct 18 ms 31788 KB n = 4, 4000000000 is a correct answer
16 Correct 21 ms 31648 KB n = 5, 4000000000 is a correct answer
17 Correct 21 ms 31768 KB n = 10, 1000000343 is a correct answer
18 Correct 19 ms 31788 KB n = 10, 3189 is a correct answer
19 Correct 19 ms 31720 KB n = 10, 7000000000 is a correct answer
20 Correct 18 ms 31784 KB n = 5, 12 is a correct answer
21 Correct 18 ms 31756 KB n = 5, 25 is a correct answer
22 Correct 18 ms 31744 KB n = 2, 122 is a correct answer
23 Correct 18 ms 31692 KB n = 10, 117 is a correct answer
24 Incorrect 18 ms 31780 KB n = 10, incorrect answer: jury 336 vs contestant 367
25 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31692 KB n = 4, 80 is a correct answer
2 Correct 18 ms 31724 KB n = 9, 110 is a correct answer
3 Correct 19 ms 31820 KB n = 4, 21 is a correct answer
4 Correct 17 ms 31692 KB n = 3, 4 is a correct answer
5 Correct 17 ms 31712 KB n = 2, 62 is a correct answer
6 Correct 18 ms 31692 KB n = 2, 3 is a correct answer
7 Correct 18 ms 31764 KB n = 3, 29 is a correct answer
8 Correct 17 ms 31792 KB n = 2, 3 is a correct answer
9 Correct 18 ms 31696 KB n = 2, 3 is a correct answer
10 Correct 18 ms 31728 KB n = 2, 2000000001 is a correct answer
11 Correct 19 ms 31652 KB n = 2, 3000000000 is a correct answer
12 Correct 18 ms 31692 KB n = 3, 3000000000 is a correct answer
13 Correct 18 ms 31724 KB n = 3, 3000000000 is a correct answer
14 Correct 18 ms 31756 KB n = 4, 3000000001 is a correct answer
15 Correct 18 ms 31788 KB n = 4, 4000000000 is a correct answer
16 Correct 21 ms 31648 KB n = 5, 4000000000 is a correct answer
17 Correct 21 ms 31768 KB n = 10, 1000000343 is a correct answer
18 Correct 19 ms 31788 KB n = 10, 3189 is a correct answer
19 Correct 19 ms 31720 KB n = 10, 7000000000 is a correct answer
20 Correct 18 ms 31784 KB n = 5, 12 is a correct answer
21 Correct 18 ms 31756 KB n = 5, 25 is a correct answer
22 Correct 18 ms 31744 KB n = 2, 122 is a correct answer
23 Correct 18 ms 31692 KB n = 10, 117 is a correct answer
24 Incorrect 18 ms 31780 KB n = 10, incorrect answer: jury 336 vs contestant 367
25 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31692 KB n = 4, 80 is a correct answer
2 Correct 18 ms 31724 KB n = 9, 110 is a correct answer
3 Correct 19 ms 31820 KB n = 4, 21 is a correct answer
4 Correct 17 ms 31692 KB n = 3, 4 is a correct answer
5 Correct 17 ms 31712 KB n = 2, 62 is a correct answer
6 Correct 18 ms 31692 KB n = 2, 3 is a correct answer
7 Correct 18 ms 31764 KB n = 3, 29 is a correct answer
8 Correct 17 ms 31792 KB n = 2, 3 is a correct answer
9 Correct 18 ms 31696 KB n = 2, 3 is a correct answer
10 Correct 18 ms 31728 KB n = 2, 2000000001 is a correct answer
11 Correct 19 ms 31652 KB n = 2, 3000000000 is a correct answer
12 Correct 18 ms 31692 KB n = 3, 3000000000 is a correct answer
13 Correct 18 ms 31724 KB n = 3, 3000000000 is a correct answer
14 Correct 18 ms 31756 KB n = 4, 3000000001 is a correct answer
15 Correct 18 ms 31788 KB n = 4, 4000000000 is a correct answer
16 Correct 21 ms 31648 KB n = 5, 4000000000 is a correct answer
17 Correct 21 ms 31768 KB n = 10, 1000000343 is a correct answer
18 Correct 19 ms 31788 KB n = 10, 3189 is a correct answer
19 Correct 19 ms 31720 KB n = 10, 7000000000 is a correct answer
20 Correct 18 ms 31784 KB n = 5, 12 is a correct answer
21 Correct 18 ms 31756 KB n = 5, 25 is a correct answer
22 Correct 18 ms 31744 KB n = 2, 122 is a correct answer
23 Correct 18 ms 31692 KB n = 10, 117 is a correct answer
24 Incorrect 18 ms 31780 KB n = 10, incorrect answer: jury 336 vs contestant 367
25 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31692 KB n = 4, 80 is a correct answer
2 Correct 18 ms 31724 KB n = 9, 110 is a correct answer
3 Correct 19 ms 31820 KB n = 4, 21 is a correct answer
4 Correct 17 ms 31692 KB n = 3, 4 is a correct answer
5 Correct 17 ms 31712 KB n = 2, 62 is a correct answer
6 Correct 18 ms 31692 KB n = 2, 3 is a correct answer
7 Correct 18 ms 31764 KB n = 3, 29 is a correct answer
8 Correct 17 ms 31792 KB n = 2, 3 is a correct answer
9 Correct 18 ms 31696 KB n = 2, 3 is a correct answer
10 Correct 18 ms 31728 KB n = 2, 2000000001 is a correct answer
11 Correct 19 ms 31652 KB n = 2, 3000000000 is a correct answer
12 Correct 18 ms 31692 KB n = 3, 3000000000 is a correct answer
13 Correct 18 ms 31724 KB n = 3, 3000000000 is a correct answer
14 Correct 18 ms 31756 KB n = 4, 3000000001 is a correct answer
15 Correct 18 ms 31788 KB n = 4, 4000000000 is a correct answer
16 Correct 21 ms 31648 KB n = 5, 4000000000 is a correct answer
17 Correct 21 ms 31768 KB n = 10, 1000000343 is a correct answer
18 Correct 19 ms 31788 KB n = 10, 3189 is a correct answer
19 Correct 19 ms 31720 KB n = 10, 7000000000 is a correct answer
20 Correct 18 ms 31784 KB n = 5, 12 is a correct answer
21 Correct 18 ms 31756 KB n = 5, 25 is a correct answer
22 Correct 18 ms 31744 KB n = 2, 122 is a correct answer
23 Correct 18 ms 31692 KB n = 10, 117 is a correct answer
24 Incorrect 18 ms 31780 KB n = 10, incorrect answer: jury 336 vs contestant 367
25 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31692 KB n = 4, 80 is a correct answer
2 Correct 18 ms 31724 KB n = 9, 110 is a correct answer
3 Correct 19 ms 31820 KB n = 4, 21 is a correct answer
4 Correct 17 ms 31692 KB n = 3, 4 is a correct answer
5 Correct 17 ms 31712 KB n = 2, 62 is a correct answer
6 Correct 18 ms 31692 KB n = 2, 3 is a correct answer
7 Correct 18 ms 31764 KB n = 3, 29 is a correct answer
8 Correct 17 ms 31792 KB n = 2, 3 is a correct answer
9 Correct 18 ms 31696 KB n = 2, 3 is a correct answer
10 Correct 18 ms 31728 KB n = 2, 2000000001 is a correct answer
11 Correct 19 ms 31652 KB n = 2, 3000000000 is a correct answer
12 Correct 18 ms 31692 KB n = 3, 3000000000 is a correct answer
13 Correct 18 ms 31724 KB n = 3, 3000000000 is a correct answer
14 Correct 18 ms 31756 KB n = 4, 3000000001 is a correct answer
15 Correct 18 ms 31788 KB n = 4, 4000000000 is a correct answer
16 Correct 21 ms 31648 KB n = 5, 4000000000 is a correct answer
17 Correct 21 ms 31768 KB n = 10, 1000000343 is a correct answer
18 Correct 19 ms 31788 KB n = 10, 3189 is a correct answer
19 Correct 19 ms 31720 KB n = 10, 7000000000 is a correct answer
20 Correct 18 ms 31784 KB n = 5, 12 is a correct answer
21 Correct 18 ms 31756 KB n = 5, 25 is a correct answer
22 Correct 18 ms 31744 KB n = 2, 122 is a correct answer
23 Correct 18 ms 31692 KB n = 10, 117 is a correct answer
24 Incorrect 18 ms 31780 KB n = 10, incorrect answer: jury 336 vs contestant 367
25 Halted 0 ms 0 KB -