Submission #1226726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226726		noyancanturk	Board Game (JOI24_boardgame)	C++20	17 / 100	41 ms	6760 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define int int64_t

#define pb push_back
#define dbg(c) for(int i=1;i<=n;i++)cerr<<c[i]<<' ';cerr<<'\n';

using pii=pair<int,int>;

const int lim=5e4+100;

vector<int>v[lim];
int stop[lim];
int fakedist[lim];
int baddist[lim],gooddist[lim];

int dist[lim],ans[lim];

signed main(){
  int n,m,k;
  cin>>n>>m>>k;
  for(int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    v[x].pb(y);
    v[y].pb(x);
  }
  string s;
  cin>>s;
  for(int i=0;i<n;i++)stop[i+1]=s[i]-'0';
  deque<int>q;
  for(int i=1;i<=n;i++){
    fakedist[i]=INT_MAX;
    if(stop[i]){
      fakedist[i]=0;
      q.pb(i);
    }
  }
  while(q.size()){
    int node=q.front();
    q.pop_front();
    for(int j:v[node]){
      if(fakedist[j]==INT_MAX){
        fakedist[j]=fakedist[node]+1;
        q.pb(j);
      }
    }
  }
  for(int i=1;i<=n;i++){
    baddist[i]=INT_MAX;
    for(int j:v[i]){
      if(fakedist[j]!=INT_MAX){
        baddist[i]=min(baddist[i],fakedist[j]+1);
      }
    }
  }
  for(int i=1;i<=n;i++){
    fakedist[i]=INT_MAX;
    if(!stop[i])continue;
    for(int j:v[i]){
      if(stop[j]){
        fakedist[i]=0;
        q.pb(i);
        break;
      }
    }
  }
  while(q.size()){
    int node=q.front();
    q.pop_front();
    for(int j:v[node]){
      if(fakedist[j]==INT_MAX){
        if(stop[j]){
          fakedist[j]=fakedist[node];
          q.push_front(j);
        }else{
          fakedist[j]=fakedist[node]+1;
          q.pb(j);
        }
      }
    }
  }
  for(int i=1;i<=n;i++){
    gooddist[i]=INT_MAX;
    for(int j:v[i]){
      if(fakedist[j]!=INT_MAX){
        gooddist[i]=min(gooddist[i],fakedist[j]+1);
      }
    }
  }
  int a[k];
  for(int i=0;i<k;i++){
    cin>>a[i];
  }
  for(int i=1;i<=n;i++)dist[i]=ans[i]=INT_MAX;
  dist[a[0]]=ans[a[0]]=0;
  q.pb(a[0]);
  unordered_set<int>changed;
  while(q.size()){
    int node=q.front();
    q.pop_front();
    for(int j:v[node]){
      if(dist[j]==INT_MAX){
        dist[j]=dist[node]+1;
        ans[j]=dist[j];
        if(stop[j]){
          changed.insert(j);
        }else{
          q.pb(j);
        }
      }
    }
  }
  if(!changed.size()){
    for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
    return 0;
  }
  int torem[n+1]{};
  int base=0,inc=0;
  for(int i=1;i<k;i++){
    base+=baddist[a[i]];
    inc+=2;
    if(gooddist[a[i]]!=INT_MAX)torem[gooddist[a[i]]-baddist[a[i]]]++;
  }
  for(int i=0;i<=n;i++){
    priority_queue<pii,vector<pii>,greater<pii>>pq;
    for(int j:changed)pq.push({dist[j],j});
    changed.clear();
    while(pq.size()){
      auto[ds,node]=pq.top();
      pq.pop();
      if(ds!=dist[node])continue;
      for(int j:v[node]){
        if(ds+1<dist[j]){
          dist[j]=ds+1;
          ans[j]=min(ans[j],dist[j]+base);
          if(stop[j]){
            changed.insert(j);
          }else{
            pq.push({dist[j],j});
          }
        }
      }
    }
    inc-=torem[i];
    base+=inc;
  }
  for(int i=1;i<=n;i++){
    cout<<ans[i]<<'\n';
  }
}

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