Submission #1202958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202958		VahanAbraham	사이버랜드 (APIO23_cyberland)	C++20	0 / 100	3098 ms	143128 KiB

cyberland

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
#include <bitset>
#include <cassert>
using namespace std;

#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen(".in", "r", stdin); freopen(".out", "w", stdout);

ll gcd(ll a, ll b)
{
    if (a == 0 || b == 0) {
        return  max(a, b);
    }
    if (a <= b) {
        return gcd(a, b % a);
    }
    else {
        return gcd(a % b, b);
    }
}
ll lcm(ll a, ll b) {
    return (a / gcd(a, b)) * b;
}

const int N = 100005;
const ll oo = 1000000000000000, MOD = 1000000007;


vector<pair<int,int>> g[N];
double dist[N][30];

double solve(int n,int m,int k,int h,vector<int> vec1,vector<int> vec2,vector<int> vec3,vector<int> a) {
    for(int i=0;i<m;++i){
        g[vec1[i]].pb({vec2[i],vec3[i]});
        g[vec2[i]].pb({vec1[i],vec3[i]});
    }
    for(int i=0;i<n;++i){
        for(int j=0;j<=k;++j){
            dist[i][j]=oo;
        }
    }
    dist[0][0]=0;
    set<pair<double,pair<int,int>>> st;
    st.insert({dist[0][0],{0,0}});
    while(1){
      int sz=st.size();
      if(sz==0){
        break;
      }
        auto it=st.begin();
        pair<double,pair<int,int>> p=(*it);
        st.erase(it);
        int k1=p.sc.fr;
        int u=p.sc.sc;
        double val=p.fr;
        if(dist[u][k1]!=val || u==h){
           continue;
        }
        double val2=val / (2.0);
        for(pair<int,int> num : g[u]){
            int h =num.fr;
            int w=num.sc;
            if(k1<k){
                if(a[u]==0){
                    if(dist[h][k1+1]>w){
                        dist[h][k1+1]=w;
                        st.insert({dist[h][k1+1],{k1+1,h}});
                    }
                    if(dist[h][k1]>val+w){
                        dist[h][k1]=val+w;
                        st.insert({dist[h][k1],{k1,h}});
                    }
                }
                else{
                    if(a[u]==2){
                        if(dist[h][k1+1]>val2+w){
                           dist[h][k1+1]=val2+w;
                           st.insert({dist[h][k1+1],{k1+1,h}});
                        }
                        if(dist[h][k1]>val+w){
                           dist[h][k1]=val+w;
                           st.insert({dist[h][k1],{k1,h}});
                        }
                    }
                    else{
                        if(dist[h][k1]>val+w){
                           dist[h][k1]=val+w;
                           st.insert({dist[h][k1],{k1,h}});
                        }
                    }
                }
            }
            else{
                if(a[u]==0){
                    if(dist[h][k1]>val+w){
                        dist[h][k1]=val+w;
                        st.insert({dist[h][k1],{k1,h}});
                    }
                }
                else{
                    if(a[u]==2){
                        if(dist[h][k1]>val+w){
                           dist[h][k1]=val+w;
                           st.insert({dist[h][k1],{k1,h}});
                        }
                    }
                    else{
                        if(dist[h][k1]>val+w){
                           dist[h][k1]=val+w;
                           st.insert({dist[h][k1],{k1,h}});
                        }
                    }
                }
            }
        }
    }
    double mn=oo;
    for(int i=0;i<=k;++i){
        mn=min(mn,dist[h][i]);
    }
    if(mn==oo){
        return -1;
    }
    return mn;
}


//https://oj.uz/problem/view/APIO23_cyberland
/*int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //US
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3