제출 #1192318

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192318		Mousa_Aboubaker	Shortcut (IOI16_shortcut)	C++20	0 / 100	1 ms	328 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;

template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

long long find_shortcut(int n, vector<int> l, vector<int> d, int C)
{
    int cnt = count_if(d.begin(), d.end(), [&](int x)
                       { return x > 0; });
    vector adj(n + cnt, vector<pair<int, int>>());
    for (int i = 0; i + 1 < n; i++)
    {
        adj[i].push_back({i + 1, l[i]});
        adj[i + 1].push_back({i, l[i]});
    }
    for (int i = 0, j = 0; i < n; i++)
    {
        if (d[i] == 0)
            continue;
        adj[i].push_back({n + j, d[i]});
        adj[n + j].push_back({i, d[i]});
        j++;
    }
    long long mn = 1e18 + 10;
    vector<long long> dis(n + cnt);
    auto bfs = [&](int start) -> long long
    {
        pqg<pair<long long, int>> pq;
        dis.assign(n + cnt, 1e18 + 10);
        pq.push({0, start});
        long long mx = 0;
        while (not pq.empty())
        {
            auto [c, u] = pq.top();
            pq.pop();

            if (dis[u] <= c)
                continue;
            dis[u] = c;
            mx = max(mx, dis[u]);
            for (auto [v, w] : adj[u])
                if(dis[v] > c + w)
                    pq.push({c + w, v});
        }
        return mx;
    };
    // set<int> edge;
    // bfs(0);
    // int xx = max_element(dis.begin(), dis.end()) - dis.begin();
    // bfs(xx);
    // xx = max_element(dis.begin(), dis.end()) - dis.begin();
    // bfs(xx);
    // priority_queue<pair<long long, int>> pq;
    // for(int i = 0; i < n + cnt; i++)
    //     pq.push({dis[i], i});
    // int y = min((int)pq.size(), 6);
    // while(y--)
    // {
    //     auto [c, v] = pq.top();
    //     pq.pop();
    //     edge.insert(v);
    // }
    // while(not pq.empty())
    // {
    //     pq.pop();
    // }
    // xx = max_element(dis.begin(), dis.end()) - dis.begin();
    // bfs(xx);
    // for(int i = 0; i < n + cnt; i++)
    //     pq.push({dis[i], i});
    // y = min((int)pq.size(), 6);
    // while(y--)
    // {
    //     auto [c, v] = pq.top();
    //     pq.pop();
    //     edge.insert(v);
    // }
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            adj[i].push_back({j, C});
            adj[j].push_back({i, C});
            long long mx = 0;
            bfs(i);
            int ss = max_element(dis.begin(), dis.end()) - dis.begin();
            mx = max(mx, dis[ss]);
            bfs(ss);
            ss = max_element(dis.begin(), dis.end()) - dis.begin();
            mx = max(mx, dis[ss]);
            bfs(ss);
            ss = max_element(dis.begin(), dis.end()) - dis.begin();
            mx = max(mx, dis[ss]);
            bfs(j);
            ss = max_element(dis.begin(), dis.end()) - dis.begin();
            bfs(ss);
            ss = max_element(dis.begin(), dis.end()) - dis.begin();
            mx = max(mx, dis[ss]);
            bfs(ss);
            ss = max_element(dis.begin(), dis.end()) - dis.begin();
            mx = max(mx, dis[ss]);
            // for (auto k: edge)
            // {
            //     long long s = bfs(k);
            //     if (mx < s)
            //         mx = s;
            // }
            if (mn > mx)
                mn = mx;
            adj[i].pop_back();
            adj[j].pop_back();
        }
    }
    return mn;
}

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

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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