제출 #1131440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131440		huutuan	Board Game (JOI24_boardgame)	C++20	14 / 100	39 ms	7160 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=5e4+10;
int n, m, k, a[N], x[N];
vector<int> g[N];

int d1[N], d2[N];

void bfs2(vector<int> root, int *d, int dd){
   for (int i=0; i<=n; ++i) d[i]=1e9;
   queue<int> q;
   for (int u:root) d[u]=0, q.push(u);
   while (q.size()){
      int u=q.front(); q.pop();
      for (int v:g[u]){
         if (d[u] && a[u]) continue;
         if (d[v]>=1e9){
            d[v]=d[u]+1;
            q.emplace(v);
         }
      }
   }
   for (int u:root) d[u]=dd;
}

int vis[N];

void bfs3(int root, vector<int> &vv){
   queue<int> q;
   vis[root]=1; q.push(root);
   while (q.size()){
      int u=q.front(); q.pop();
      vv.push_back(u);
      for (int v:g[u]){
         if (!vis[v] && a[v]){
            vis[v]=1;
            q.emplace(v);
         }
      }
   }
}

int f[N][2];

void dijkstra(int root, int sum1, int sum2){
   for (int i=0; i<=n; ++i) f[i][0]=f[i][1]=1e18;
   priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
   pq.push({f[root][0]=0, {root, 0}});
   while (pq.size()){
      int u=pq.top().second.first, cnt=pq.top().second.second, dist=pq.top().first;
      pq.pop();
      if (f[u][cnt]!=dist) continue;
      if (u!=root && a[u]){
         if (!cnt) dist+=sum1;
         else dist+=sum2;
         cnt=1;
      }
      for (int v:g[u]){
         if (f[v][cnt]>dist+1){
            pq.push({f[v][cnt]=dist+1, {v, cnt}});
         }
      }
   }
}

int ans[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m >> k;
   for (int i=1; i<=m; ++i){
      int u, v; cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
   }
   string s; cin >> s;
   for (int i=1; i<=n; ++i) a[i]=s[i-1]=='1';
   for (int i=1; i<=k; ++i) cin >> x[i];
   vector<int> v1, v2;
   for (int i=1; i<=n; ++i) if (a[i] && !vis[i]){
      vector<int> v;
      bfs3(i, v);
      if ((int)v.size()==1) v1.insert(v1.end(), v.begin(), v.end());
      else v2.insert(v2.end(), v.begin(), v.end());
   }
   bfs2(v1, d1, 2);
   bfs2(v2, d2, 1);
   memset(ans, 0x3f, sizeof ans);
   vector<pair<int, int>> v;
   for (int j=2; j<=k; ++j){
      v.emplace_back(d1[x[j]], d2[x[j]]);
   }
   sort(v.begin(), v.end(), [&](pair<int, int> t1, pair<int, int> t2){
      return t1.first-t1.second<t2.first-t2.second;
   });
   for (int i=0; i<=k-1; ++i){
      if (v2.empty() && i!=k-1) continue;
      if (v1.empty() && i) continue;
      int sum1=0, sum2=i*2+(k-1-i);
      for (int j=0; j<i; ++j) sum1+=v[j].first;
      for (int j=i; j<k-1; ++j) sum1+=v[j].second;
      dijkstra(x[1], sum1, sum2);
      for (int j=1; j<=n; ++j) ans[j]=min({ans[j], f[j][0], f[j][1]});
   }
   for (int i=1; i<=n; ++i) cout << ans[i] << '\n';
   return 0;
}

• Subtask 1: 0 / 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