제출 #1160294

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

Main

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 5000+100, M = 1e5+10, K = 52, MX = 30;


int n, m, k, A[N], dp[N][N], X[N], dp2[N][N];
pii Y[N];
vector<int> g[N];
string s;
void solve(){
  cin >> n >> m >> k;
  for(int i = 1; i <= m; ++i){
    int u, v; cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
  }
  cin >> s;
  s = " " + s;
  for(int i = 1; i <= k; ++i){
    cin >> A[i];
  }
  for(int i = 1; i <= n; ++i){
    X[i] = MOD;
    Y[i] = {MOD, MOD};
  }
  priority_queue<array<int, 3>> q;
  vector<bool> vis(n+1);
  for(int i = 1; i <= n; ++i){
    if(s[i] == '1'){
      X[i] = 0;
      q.push({0, 0, i});
    }
  }
  while(!q.empty()){
    int v = q.top()[2]; q.pop();
    if(vis[v]) continue;
    vis[v] = 1;
    for(int u: g[v]){
      if(X[u] > X[v] + 1){
        X[u] = X[v] + 1;
        q.push({-X[u], 0, u});
      }
    }
  }
  // vis.clear();
  // vis.resize(n+1);
  // for(int i = 1; i <= n; ++i){
  //   if(s[i] == '0'){
  //     for(int j: g[i]){
  //       if(s[j] == '0'){
  //         Y[i] = {0, 0};
  //       }
  //     }
  //     if(Y[i].ff == 0) q.push({0, 0, i});
  //   }
  // }
  // while(!q.empty()){
  //   int v = q.top()[2]; q.pop();
  //   if(vis[v]) continue;
  //   vis[v] = 1;
  //   int cost = 1 + (s[v] == '0');
  //   for(int u: g[v]){
  //     if(Y[u].ff > Y[v].ff + cost){
  //       Y[u].ff = Y[v].ff + cost;
  //       Y[u].ss = Y[v].ss + cost - 1;
  //       q.push({-Y[u].ff, -Y[u].ss, u});
  //     }else if(Y[u].ff == Y[v].ff + cost && Y[u].ss > Y[v].ss + cost - 1){
  //       Y[u].ss = Y[v].ss + cost - 1;
  //       q.push({-Y[u].ff, -Y[u].ss, u});
  //     }
  //   }
  // }

  for(int i = 0; i <=n ; ++i) for(int j = 0; j <= n; ++j) dp[i][j] = MOD;
  dp[A[1]][0] = 0;
  for(int j = 0; j <= n; ++j){ // number of zeros
    priority_queue<pair<int, int>> Q;
    vector<bool> used(n + 5);
    for(int i = 1; i <= n; ++i){
      Q.push({-dp[i][j], i});
    }
    while(!Q.empty()){
      int v = Q.top().ss;
      Q.pop();
      if(used[v]) continue;
      used[v] = 1;
      for(int u: g[v]){
        if(s[u] == '1'){
          if(dp[v][j] + 1 < dp[u][j + 1]){
            dp[u][j + 1] = dp[v][j] + 1;
          }
        }else{
          if(dp[v][j] + 1 < dp[u][j]){
            dp[u][j] = dp[v][j] + 1;
            Q.push({-dp[u][j], u});
          }
        }
      }
    }
    // en;
    // for(int i = 1; i <= n; ++i){
    //   cout << dp[i][j] << ' ';
    // }
  }

  for(int i = 0; i <=n ; ++i) for(int j = 0; j <= n; ++j) dp2[i][j] = MOD;
  dp2[A[2]][0] = 0;
  for(int j = 0; j <= n; ++j){ // number of zeros
    priority_queue<pair<int, int>> Q;
    vector<bool> used(n + 5);
    for(int i = 1; i <= n; ++i){
      Q.push({-dp2[i][j], i});
    }
    while(!Q.empty()){
      int v = Q.top().ss;
      Q.pop();
      if(used[v]) continue;
      used[v] = 1;
      for(int u: g[v]){
        if(s[u] == '1'){
          if(dp2[v][j] + 1 < dp2[u][j + 1]){
            dp2[u][j + 1] = dp2[v][j] + 1;
          }
        }else{
          if(dp2[v][j] + 1 < dp2[u][j]){
            dp2[u][j] = dp2[v][j] + 1;
            Q.push({-dp2[u][j], u});
          }
        }
      }
    }
  }

  vector<int> best(n+5);
  for(int j = 1; j <= n; ++j){  
    int cost2 = MOD;
    for(int v = 1; v <= n; ++v) cost2 = min(cost2, dp2[v][j]);
    best[j] += min(s[A[2]] == '1' ? j * 2 : X[A[2]] + (j-1)*2, cost2);
  }
  for(int i = 1; i <= n; ++i){
    int ans = MOD;
    for(int j = 0; j <= n; ++j){
      if(s[i] == '1' && j > 0)
        ans = min(ans, dp[i][j] + best[j - 1]);
      else
        ans = min(ans, dp[i][j] + best[j]);
    }
    cout << ans << '\n';
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\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