Submission #1164262

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

Main

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
vector<vector<long long>> DP;
vector<vector<int>> graph;
string s;
void dijik(int n,int cnt,vector<int> &source){
    DP.clear();
    DP.resize(n+1);
    for(int i=1;i<=n;i++){
        DP[i].clear();
        DP[i].resize(cnt+1);
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=cnt;j++){
            DP[i][j]=1e18;
        }
    }
    priority_queue<pair<long long,pair<int,int>>,vector<pair<long long,pair<int,int>>>,greater<pair<long long,pair<int,int>>>> pq;
    for(int i=0;i<source.size();i++){
        DP[source[i]][0]=0;
        pq.push({0,{source[i],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}});
                }
            }
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m,k;
    cin >> n >> m >> k;
    graph.clear();
    graph.resize(n+1);
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    cin >> s;
    s='#'+s;
    int x[k];
    vector<int> source;
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='1'){
            cnt++;
            source.push_back(i);
        }
    }
    int dist[n+1];
    dijik(n,1,source);
    for(int i=1;i<=n;i++){
        dist[i]=DP[i][(s[i]=='1')];
    }
    long long tot[n+1]={0};
    tot[0]=0;
    source.clear();
    source.resize(0);
    for(int i=1;i<=n;i++){
        if(s[i]=='1'){
            for(int v:graph[i]){
                if(s[v]=='1'){
                    source.push_back(i);
                    break;
                }
            }
        }
    }
    dijik(n,cnt,source);
    for(int i=0;i<k;i++){
        cin >> x[i];
        if(i==0){
            continue;
        }
        long long cost[cnt+1];
        for(int j=0;j<=cnt;j++){
            cost[j]=1e18;
        }
        cost[0]=0;
        for(int j=1;j<=cnt;j++){
            cost[j]=min(cost[j],DP[x[i]][j-1+(s[x[i]]=='1')]);
            if(j>1){
                cost[j]=min(cost[j],cost[j-1]+1);
            }
        }
        for(int j=1;j<=cnt;j++){
            cost[j]=min(cost[j],1LL*dist[x[i]]+2*(j-1));
            tot[j]+=cost[j];
        }
    }
    source.clear();
    source.resize(0);
    source.push_back(x[0]);
    dijik(n,cnt,source);
    long long ans[n+1];
    for(int u=1;u<=n;u++){
        ans[u]=1e18;
        if(u==x[0]){
            ans[u]=0;
        }
        else{
            for(int j=0;j+(s[u]=='1')<=cnt;j++){
                ans[u]=min(ans[u],DP[u][j+(s[u]=='1')]+tot[j]);
            }
        }
        cout << ans[u] << endl;
    }
}

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