제출 #1163627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163627		dnnnda	Board Game (JOI24_boardgame)	C++20	0 / 100	391 ms	39820 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
//#pragma GCC optimize("O3")
#define init(arr,val) memset(arr,val,sizeof arr)
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
const int X=1000000007;
//const int X=998244353;

vector<int> adj[50004];
int x[50004], st[3003];
ll cost[3003];

int main(){
    //ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m, k; cin >> n >> m >> k;
    for(int i=1 ; i<=m ; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    string s; cin >> s;
    s="."+s;
    for(int i=1 ; i<=k ; i++) cin >> x[i];

    for(int i=1 ; i<=n ; i++){
        if(s[i]=='0') continue;
        st[i]=1;
        for(int v:adj[i]) if(s[v]=='1') st[i]=2;
    }
    for(int i=1 ; i<=n ; i++){
        int dis1=inf, dis2=inf;
        queue<int> q;
        q.push(x[i]);
        bitset<3003> vis;
        vector<int> d(3003,inf);
        d[x[i]]=0;
        vis[x[i]]=1;
        while(!q.empty()){
            int u=q.front();
            q.pop();
            if(st[u]==1) dis1=d[u];
            if(st[u]==2) dis2=d[u];
            for(int v:adj[u]) if(!vis[v]){
                vis[v]=1;
                d[v]=d[u]+1;
                q.push(v);
            }
        }
        cost[1]+=min(dis1,dis2);
        for(int j=2 ; j<=n ; j++){
            cost[j]+=min(dis1+2*(j-1),dis2+(j-1));
        }
    }

    queue<pair<int,int>> q;
    bitset<3003> vis[3003];
    q.push({x[1],0});
    vis[x[1]][0]=1;
    int d[3003][3003];
    init(d,0x3f);
    d[x[1]][0]=0;

    while(!q.empty()){
        auto[u,t]=q.front();
        q.pop();
        for(int v:adj[u]){
            if(u==x[1]||s[u]=='0'){
                if(!vis[v][t]){
                    vis[v][t]=1;
                    d[v][t]=d[u][t]+1;
                    q.push({v,t});
                }
            }
            else{
                if(!vis[v][t+1]){
                    vis[v][t+1]=1;
                    d[v][t+1]=d[u][t]+1;
                    q.push({v,t+1});
                }
            }
        }
    }

    for(int i=1 ; i<=n ; i++){
        ll ans=inff;
        for(int c=0 ; c<=n ; c++) ans=min(ans,d[i][c]+cost[c]);
        cout << ans << '\n';
    }


    return 0;
}

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