제출 #433369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
433369		Monchito	Shortcut (IOI16_shortcut)	C++14	0 / 100	21 ms	31820 KiB

shortcut

#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);
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3