| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 926999 | lumid | 사이버랜드 (APIO23_cyberland) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Source: https://usaco.guide/general/io
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#include <chrono>
#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
#include <iterator>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
#define inp(n, a) vector<ll> a;for(int i=0;i<n;i++){ll now;cin>>now;a.pb(now);}
#define all(a) a.begin(),a.end()
#define show(a) for(long long loppls=0;loppls<(long long)(a.size()-1);loppls++)cout<<a[loppls]<<' ';cout<<a[a.size()-1];
#ifdef reimufumo
#define owo(x) std::cerr << x;
#define ovo(a) for(long long loppls=0;loppls<(long long)(a.size()-1);loppls++)cerr<<a[loppls]<<' ';cerr<<a[a.size()-1];
#define ouo(a,x) for(long long loppls=0;loppls<x-1;loppls++)cerr<<a[loppls];cerr<<a[x-1];
#define dbg(x) std::cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << std::endl
#define dbgif(cond, x) ((cond) ? std::cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << std::endl : std::cerr)
#else
#define owo(x) ((void)0)
#define ovo(a) ((void)0)
#define ouo(a,x) ((void)0)
#define dbg(x) ((void)0)
#define dbgif(cond, x) ((void)0)
#endif
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
long long inv(long long a, long long p){
return binpow(a, p-2, p);
}
vector<ll> fact; // must be init if nCk needed
long long nCk(long long n, long long k, long long p){
return ((fact[n] * inv(fact[k], p) % p) * inv(fact[n-k], p)) % p;
}
ll sum2(ll a, ll l, ll n){return (n*(a+l))/2;}
ll ceil2(ll a, ll b){ll c=a/b;if(a%b!=0)c++;return c;}
ll floor2(ll x, ll m){ll r=(x%m+m)%m;return (x-r)/m;}
const ll INF=1e16,MAX=100020,MOD=998244353;
ll n,m,k,h;
vector<int> arri;
vector<vector<vector<ll>>> adj; // adj[u] {v,w,type}
vector<double> dist;
vector<bool> processed;
vector<vector<ll>> dfsadj;
vector<bool> visited;
vector<ll> can;
void init(){
adj.clear();
dist.clear();
processed.clear();
dfsadj.clear();
visited.clear();
can.clear();
for(int i=0;i<=(k+1)*n;i++){
dfsadj.pb({});
adj.pb({});
visited.pb(0);
}
}
void dijkInit(){
dist.clear();
processed.clear();
for(int i=0;i<=(k+1)*n;i++){
dist.pb(INF); // check on this because of the double
processed.pb(0);
}
}
double calc(double d,ll w,ll typ){ // todo: calculate distance
if(typ==1){
return (double)(d)+(double)(w);
}else if(typ==0){
return 0.0;
}else{
return (double)(((double)(d)+(double)(w))/2.0);
}
}
void dijkstra(){
priority_queue<tuple<ll,double,ll>> q;
for(ll u:can){
if(u==h)continue;
q.push({0,0,-u});
dist[u]=0;
}
q.push({0,0,0});
dist[0]=0;
while(!q.empty()){
owo(get<0>(q.top()));owo(' ');
owo(get<1>(q.top()));owo(' ');
owo(get<2>(q.top()));owo(' ');
owo(q.size());owo('\n');
ll u=-1*(get<0>(q.top()))*n-get<2>(q.top());q.pop();
//owo("u: ");owo(u);owo('\n');
if(processed[u])continue;
processed[u]=1;
for(vector<ll> node:adj[u]){
ll v=node[0],w=node[1],typ=node[2];
double distnow=calc(dist[u],w,typ);
if(distnow<dist[v]){
dist[v]=distnow;
q.push({-((v-(v%n))/n),-dist[v],-(v%n)});
//owo(-((v-(v%n))/n));owo(' ');owo(-dist[v]);owo(' ');owo(v%n);owo('\n');
}
}
//owo('\n');
}
}
void dfs(ll u){
if(visited[u])return;
visited[u]=1;
if(u==h)return;
if(arri[u]==0)can.pb(u);
for(ll v:dfsadj[u])dfs(v);
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
#ifdef reimufumo
auto chrono_begin = chrono::steady_clock::now();
#endif
// THIS PROBLEM IS 0-INDEXED
n=N,m=M,k=min(70,K),h=H;
arri=arr;
init();
#ifdef reimufumo
cerr << "chrono: " << 1e-6L * chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now() - chrono_begin).count() << 's' << '\n';
#endif
for(int i=0;i<m;i++){ // whaaaaaaaaat
ll u=x[i],v=y[i],w=c[i];
dfsadj[u].pb(v);dfsadj[v].pb(u);
ll typ1=arr[u],typ2=arr[v];
for(int j=0;j<k;j++){
if(v!=h && typ1==0) adj[j*n+v].pb({j*n+u,0,0});
else if(v!=h) adj[j*n+v].pb({j*n+u,w,1});
if(u!=h && typ2==0) adj[j*n+u].pb({j*n+v,0,0});
else if(u!=h) adj[j*n+u].pb({j*n+v,w,1});
if(v!=h && typ1==2) adj[j*n+v].pb({(j+1)*n+u,w,2});
if(u!=h && typ2==2) adj[j*n+u].pb({(j+1)*n+v,w,2});
}
if(v!=h && typ1==0) adj[k*n+v].pb({k*n+u,0,0});
else if(v!=h) adj[k*n+v].pb({k*n+u,w,1});
if(u!=h && typ2==0) adj[k*n+u].pb({k*n+v,0,0});
else if(u!=h) adj[k*n+u].pb({k*n+v,w,1});
}
// rmb to join down fencengtu
/*for(int i=0;i<k;i++){
for(int j=0;j<n;j++){
adj[i*n+j].pb({(i+1)*n+j,0,1});
}
}*/
#ifdef reimufumo
cerr << "chrono: " << 1e-6L * chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now() - chrono_begin).count() << 's' << '\n';
#endif
dfs(0);
//can.pb(0);
if(!visited[h])return -1;
#ifdef reimufumo
cerr << "chrono: " << 1e-6L * chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now() - chrono_begin).count() << 's' << '\n';
#endif
dijkInit();
dijkstra();
double ans=INF;
for(int i=0;i<=k;i++){
ans=min(ans,dist[i*n+h]);
}
return (ans>=1e12?-1:ans); // beware of double precision
}
#ifdef reimufumo
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
vector<double> checklater;
ll tctc;cin>>tctc;
while(tctc--){
int ninp,minp,kinp,hinp;cin>>ninp>>minp>>kinp>>hinp;
vector<int> xinp,yinp,cinp,arrinp;
for(int i=0;i<ninp;i++){
int arrnow;cin>>arrnow;
arrinp.pb(arrnow);
}
for(int i=0;i<minp;i++){
int xnow,ynow,cnow;cin>>xnow>>ynow>>cnow;
xinp.pb(xnow);yinp.pb(ynow);cinp.pb(cnow);
}
double ans=solve(ninp,minp,kinp,hinp,xinp,yinp,cinp,arrinp);
cout<<ans<<'\n';
checklater.pb(ans);
/*for(int i=0;i<=3;i++){
for(int j=0;j<n;j++){
cerr<<dist[i*n+j]<<' ';
}cerr<<'\n';
}*/
}
cout<<'\n';
ll counting=0;
for(double cl:checklater){
counting++;
double cn;cin>>cn;
if(abs(cl-cn)>1){
cout<<counting<<": "<<cl<<' '<<cn<<'\n';
}
}
}
#endif