제출 #1211885

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

shortcut

//#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<pair<int,ll>>> cad;
ll a, b, c;
ll asd(int d)
{
    cad[a].push_back({b,c});
    cad[b].push_back({a,c});
    priority_queue<pair<ll,ll>> q;
    vector<ll> v(cad.size()+1,-1);
    q.push({0,d});
    ll asd=0;
    while(!q.empty())
    {
        pair<ll,ll> temp=q.top();q.pop();
        if(v[temp.second]==-1)
        {
            v[temp.second]=-temp.first;
            asd=max(asd,v[temp.second]);
            for(auto i:cad[temp.second])
            {
                if(v[i.first]==-1)
                    q.push({temp.first-i.second,i.first});
            }
        }
    }
    cad[a].pop_back();
    cad[b].pop_back();
    return asd;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int C)
{
    cad.resize(2*n+5);
    for(int i=0; i<n-1; i++)
    {
        cad[i].push_back({i+1,l[i]});
        cad[i+1].push_back({i,l[i]});
        cad[i].push_back({n+i,d[i]});
        cad[n+i].push_back({i,d[i]});
    }
    cad[n-1].push_back({n-1+n,d[n-1]});
    cad[n-1+n].push_back({n-1,d[n-1]});
    ll p1=1e9;
    ll p2=-1;
    for(int i=0; i<n; i++)
    {
        if(d[i]!=0)
        {
            p1=min(p1,(ll)i+n);
        }
        if(d[i]!=0)
        {
            p2=max(p2,(ll)i+n);
        }
    }
    ll ans=1e17;
    c=C;
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            a=i;b=j;
            ans=min(ans,max(max(asd(0),asd(n-1)),max(asd(p1),asd(p2))));
        }
    }
    return ans;
}

컴파일 시 표준 에러 (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