Submission #1164186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164186		KhoaDuy	Board Game (JOI24_boardgame)	C++17	17 / 100	527 ms	1114112 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
vector<int> dijik(int n,vector<vector<int>> &graph,vector<int> &init){
    vector<int> bst(n+1);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    for(int i=1;i<=n;i++){
        pq.push({init[i],i});
        bst[i]=init[i];
    }
    while(!pq.empty()){
        int u=pq.top().second,dist=pq.top().first;
        pq.pop();
        if(dist>bst[u]){
            continue;
        }
        for(int v:graph[u]){
            if(bst[v]>dist+1){
                bst[v]=dist+1;
                pq.push({bst[v],v});
            }
        }
    }
    return bst;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m,k;
    cin >> n >> m >> k;
    vector<vector<int>> graph(n+1);
    int cnt=0;
    int coef=2;
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    string s;
    cin >> s;
    s='#'+s;
    vector<int> init(n+1);
    for(int i=1;i<=n;i++){
        init[i]=1e9;
    }
    for(int i=1;i<=n;i++){
        if(s[i]=='1'){
            cnt++;
            init[i]=0;
        }
    }
    for(int u=1;u<=n;u++){
        for(int v:graph[u]){
            if(s[u]=='1'&&s[v]=='1'){
                coef=1;
            }
        }
    }
    int x[k];
    vector<int> dist=dijik(n,graph,init);
    long long sum=0;
    for(int i=0;i<k;i++){
        cin >> x[i];
        if(i>0){
            if(s[x[i]]=='0'){
                sum+=dist[x[i]];
            }
            else{
                sum+=coef;
            }
        }
    }
    long long ans[n+1];
    long long DP[n+1][cnt+1];
    for(int i=1;i<=n;i++){
        for(int j=0;j<=cnt;j++){
            DP[i][j]=1e18;
        }
    }
    DP[x[0]][0]=0;
    priority_queue<pair<long long,pair<int,int>>,vector<pair<long long,pair<int,int>>>,greater<pair<long long,pair<int,int>>>> pq;
    pq.push({0,{x[0],0}});
    while(!pq.empty()){
        long long dist=pq.top().first;
        int u=pq.top().second.first,c=pq.top().second.second;
        pq.pop();
        if(dist>DP[u][c]){
            continue;
        }
        for(int v:graph[u]){
            if(s[v]=='0'){
                if(DP[v][c]>dist+1){
                    DP[v][c]=dist+1;
                    pq.push({DP[v][c],{v,c}});
                }
            }
            else if(s[v]=='1'&&c<cnt){
                if(DP[v][c+1]>dist+1){
                    DP[v][c+1]=dist+1;
                    pq.push({DP[v][c+1],{v,c+1}});
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        ans[i]=1e18;
        if(s[i]=='0'){
            ans[i]=min(ans[i],DP[i][0]);
            if(cnt>=1){
                ans[i]=min(ans[i],DP[i][1]+sum);
            }
            if(cnt>=2){
                ans[i]=min(ans[i],DP[i][2]+sum+coef*(k-1));
            }
        }
        else{
            ans[i]=min(ans[i],DP[i][1]);
            if(cnt>=2){
                ans[i]=min(ans[i],DP[i][2]+sum);
            }
        }
        cout << ans[i] << endl;
    }
}

• Subtask 1: 3 / 3
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 9
• Subtask 7: 0 / 23
• Subtask 8: 0 / 9