QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#624614 | #5540. City Hall | Oldera | WA | 183ms | 30548kb | C++17 | 5.7kb | 2024-10-09 16:15:03 | 2024-10-09 16:15:04 |
Judging History
answer
#pragma GCC optimize ("O3")
//#incluse <bits/stdc++.h>
#include <iostream> // Input/output stream objects
#include <fstream> // File stream objects
#include <sstream> // String stream objects
#include <iomanip> // Input/output manipulators
#include <string> // String class and functions
#include <vector> // Dynamic array
#include <list> // Doubly linked list
#include <set> // Set container
#include <map> // Map container
#include <queue> // Queue container
#include <stack> // Stack container
#include <algorithm> // Algorithms on sequences (e.g., sort, find)
#include <cmath> // Mathematical functions
#include <ctime> // Date and time functions
#include <cstdlib> // General purpose functions (e.g., memory management)
#include <cstring> // C-style string functions
#include <cctype> // Character classification functions
#include <cassert> // Assert function for debugging
#include <exception> // Standard exceptions
#include <functional> // Function objects
#include <iterator> // Iterator classes
#include <limits> // Numeric limits
#include <locale> // Localization and internationalization
#include <numeric> // Numeric operations (e.g., accumulate)
#include <random> // Random number generators
#include <stdexcept> // Standard exception classes
#include <typeinfo> // Runtime type information
#include <utility> // Utility components (e.g., std::pair)
#include <tuple>
#include <cstdio>
#include <bitset>
using namespace std;
// ************ Setting up ************
#define FPTU ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define BUG(x) {cerr << #x << " = " << x << endl;}
#define pii pair<int,int>
#define pip pair<int,pii>
#define ppi pair<pii,int>
#define ll long long
#define ull unsigned long long
#define usi unsigned int
#define pll pair<ll,ll>
#define plp pair<ll,pll>
#define ppl pair<pll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define oo 1000111000
#define ooo 1000111000111000111
#define inf 0x3f //4557430888798830399
#define fi first
#define se second
#define vt vector
#define pb push_back
#define all(arr) arr.begin(),arr.end()
#define bit(n, i) (((n) >> (i)) & 1)
#define db(x) cerr << #x << " = " << (x) << '\n';
ll rand_num(ll a,ll b) {
random_device rd; mt19937 mt(rd()); uniform_int_distribution<ll> dist(a,b);
return dist(mt);
}
int mod=1e9+7; // MODDDDDDDDDDDDD
template <typename T> void minimize(T &a, T b){ if(a>b) a=b; }
template <typename T> void maximize(T &a, T b){ if(a<b) a=b; }
template <typename T> void add(T &a, T b){ a+=b; if(a>=mod) a-=mod; }
template <typename T> T gcd(T a, T b){
while(a!=0&&b!=0) if(a>b) a%=b; else b%=a; return a+b; }
void read_file()
{
freopen("sample.inp","r",stdin);
freopen("sample.out","w",stdout);
}
// =========> <3 VietHai1709 <3 <=========
struct line{
ll a,b;
line(ll x=0,ll y=ooo)
{
a=x; b=y;
}
ll get(ll x)
{
return a*x+b;
}
};
struct ConvextHullTrick{
int n;
int flag;
vt<line> Line;
ConvextHullTrick(){
n=0;
flag=0;
Line.clear();
}
bool bad(line u,line v,line w)
{
//return (double)(u.b-w.b)/(w.a-u.a)<=(double)(u.b-v.b)/(v.a-u.a);
// giao(u,w) <= giao(u,v) -> pop line v
return (u.b-w.b)*(v.a-u.a)<=(u.b-v.b)*(w.a-u.a);
}
void add(line L)
{
while(n>=2 && bad(Line[n-2],Line[n-1],L))
{
Line.pop_back();
n--;
}
Line.pb(L);
n++;
}
ll query(ll x)
{
if(flag>n-1) flag=n-1;
while(flag+1<n && Line[flag].get(x)>Line[flag+1].get(x)) flag++;
return Line[flag].get(x);
}
};
void Dijktra(int st,vt<vt<pair<int,ll>>> Edge, vt<ll> &dis)
{
dis[st]=0;
priority_queue<pli,vt<pli>,greater<pli>> pq;
pq.push({0,st});
while(!pq.empty())
{
pli k=pq.top(); pq.pop();
int u = k.se;
ll w = k.fi;
if (w > dis[u]) continue;
for(auto &[v,x]: Edge[u]) {
if (dis[v] > w + x) {
dis[v] = x + w;
pq.push({dis[v], v});
}
}
}
}
ll dis(ll a,ll b){
return (a-b)*(a-b);
}
bool cmp(line &a, line &b){
if(a.a!=b.a) return a.a>b.a;
return a.b<b.b;
}
void Minnnnnnn()
{
int n,m,s,t;
cin>>n>>m>>s>>t;
vt<ll> h(n+1);
for(int i=1;i<=n;i++) cin>>h[i];
vt<vt<pair<int,ll>> > ke(n+1);
while(m--){
int u,v;
cin>>u>>v;
ll w=dis(h[u],h[v]);
ke[u].pb({v,w});
ke[v].pb({u,w});
}
vt<ll> F(n+1,ooo);
vt<ll> G(n+1,ooo);
Dijktra(s, ke, F);
Dijktra(t, ke, G);
ll ans=ooo;
for(auto &[u,_]:ke[s]) ans=min(ans,G[u]*2);
for(auto &[u,_]:ke[t]) ans=min(ans,F[u]*2);
//cout<<setprecision(2)<<fixed<<ans/2.0<<'\n';
for(int i=1;i<=n;i++) if(i!=s && i!=t){
ConvextHullTrick myCHT;
vt<line> a;
for(auto &[u,_]:ke[i]){
a.pb(line(h[u]*2, h[u]*h[u] + G[u]*2));
}
sort(all(a),cmp);
for(line x:a) myCHT.add(x);
for(auto &[u,_]:ke[i]){
ans=min(ans, F[u]*2+h[u]*h[u]+myCHT.query(-h[u]));
}
}
cout<<setprecision(2)<<fixed<<ans/2.0;
}
int main(){
FPTU; //fast
//read_file();
int __=1;
//cin>>__;
for(int _=1;_<=__;_++)
{
Minnnnnnn();
}
cerr << "Time elapsed: " << TIME << " s.\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3916kb
input:
5 6 1 3 5 100 8 2 10 1 2 2 3 2 5 1 4 4 5 3 5
output:
4.50
result:
ok found '4.5000000', expected '4.5000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
5 5 1 5 1 2 10 10 4 1 2 2 3 2 4 3 5 4 5
output:
3.00
result:
ok found '3.0000000', expected '3.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3980kb
input:
5 4 1 4 8 8 8 8 100 1 2 2 3 3 4 4 5
output:
0.00
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
2 1 1 2 0 100000 1 2
output:
0.00
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 73ms
memory: 26176kb
input:
632 199396 167 549 22513 93521 41403 35441 97617 53210 62622 4751 81863 14470 2994 93092 40432 30872 34423 36577 92540 92961 4110 14691 83321 10680 89112 80890 31108 24492 8973 42636 33792 27400 82361 85003 68940 31221 48625 276 52755 6649 34381 54399 6063 22628 17715 54052 58175 86609 82622 29917 9...
output:
0.00
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #6:
score: 0
Accepted
time: 65ms
memory: 22036kb
input:
600 179700 396 574 83219 94660 9266 1939 32637 7117 33396 76947 42614 41001 87026 60210 25868 36044 35276 6147 36198 25195 50981 68230 32619 62563 28509 46643 43304 36195 99724 30903 77230 57923 36939 81397 17374 90947 48623 38120 48914 96481 98146 31707 9427 58735 82986 31328 94507 69081 51908 4188...
output:
0.00
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #7:
score: 0
Accepted
time: 168ms
memory: 29656kb
input:
100000 200000 66364 98254 48399 8344 35365 18555 95271 13113 75220 25062 73969 71647 58212 68205 36310 45496 6965 59960 71592 81323 44341 95796 61521 63298 77830 16145 73103 83477 85246 53680 67289 68475 64978 43576 18969 28023 22848 55164 31276 12825 70999 49142 77203 40134 88148 59337 2357 70519 8...
output:
1019365473.00
result:
ok found '1019365473.0000000', expected '1019365473.0000000', error '0.0000000'
Test #8:
score: 0
Accepted
time: 172ms
memory: 30548kb
input:
100000 200000 21412 38673 24050 75090 3692 20770 26840 57646 61096 3013 66291 73437 83126 67768 92979 69169 9389 70447 17151 74737 33407 3128 78504 52736 45853 27090 64395 24808 83577 24168 38576 37445 71022 40066 34908 90579 58370 31436 69812 39811 83370 50254 6518 72740 79316 67247 22759 65630 564...
output:
0.00
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #9:
score: -100
Wrong Answer
time: 183ms
memory: 30524kb
input:
100000 200000 75283 45047 38593 5224 81049 28255 11324 43744 51172 60916 67783 62336 96782 50029 48743 18780 32756 4774 32484 95733 17336 38046 98145 49655 68352 58308 21594 64540 11719 57827 30130 70076 95133 29886 93864 22677 28498 60413 44567 78935 64952 88954 85786 34019 75159 69192 15108 54645 ...
output:
449627765.00
result:
wrong answer 1st numbers differ - expected: '6010044.5000000', found: '449627765.0000000', error = '73.8127181'