Submission #1163660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163660		dnnnda	Board Game (JOI24_boardgame)	C++20	0 / 100	427 ms	45888 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[50004], d[3003][3003];
bool vis[3003][3003];
ll cost[50003];

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++) cout << st[i] << ' ';
    //cout << '\n';
    for(int i=2 ; i<=k ; i++){
        int dis1=inf, dis2=inf;
        queue<int> q;
        q.push(x[i]);
        bitset<3003> _vis;
        _vis.reset();
        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=min(dis1,_d[u]);
            if(st[u]==2) dis2=min(dis2,_d[u]);
            for(int v:adj[u]) if(!_vis[v]){
                _vis[v]=1;
                _d[v]=_d[u]+1;
                q.push(v);
            }
        }

        //cout << i << ' ' << dis1 << ' ' << dis2 << '\n';

        cost[1]+=min(dis1==0 ? 2 : dis1,dis2==0 ? 1 : dis2);
        for(int j=2 ; j<=n ; j++){
            cost[j]+=min((dis1==0 ? 2 : dis1)+2*(j-1),(dis2==0 ? 1 : dis2)+(j-1));
        }
    }
    //for(int i=1 ; i<=n ; i++) cout << cost[i] << ' ';
    //cout << '\n';

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

    while(!q.empty()){
        auto[u,t]=q.front();
        //cout << u << ' ' << t << '\n';
        q.pop();
        for(int v:adj[u]){
            if(u==1&&t==0||s[u]=='0'){
                if(!vis[v][t]){
                    vis[v][t]=1;
                    d[v][t]=d[u][t]+1;
                    q.push({v,t});
                }
            }
            else{
                if(t+1<=n&&!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