제출 #1318292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318292		user736482	Board Game (JOI24_boardgame)	C++20	40 / 100	59 ms	11048 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define INF 1000000001LL
#define POT (1LL<<23)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define vvi vector<vi>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define X 18
#define FCTCST 7
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U,typename Z>
pair<T, U> operator*(const pair<T, U>& a, const Z& b) {
    return {a.first*b, a.second*b};
}
template<typename T, typename U,typename Z>
pair<T, U> operator/(const pair<T, U>& a, const Z& b) {
    return {a.first/b, a.second/b};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os<<"{"<<p.ff<<", "<<p.ss<<"}";
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i) os << ", ";
        os << v[i];
    }
    os << "}";
    return os;
}
template<ll MOD=998244353>
struct mint_t{
    ll x;
    mint_t(ll y=0){x=y%MOD;if(x<0)x+=MOD;}
    mint_t& operator+=(const mint_t& a){if((x+=a.x)>=MOD)x-=MOD;return *this;}
    mint_t& operator-=(const mint_t& a){if((x+=MOD-a.x)>=MOD)x-=MOD;return *this;}
    mint_t operator+(const mint_t& a)const{mint_t res(*this);return res+=a;}
    mint_t operator-(const mint_t& a)const{mint_t res(*this);return res-=a;}
    mint_t& operator*=(const mint_t& a){(x*=a.x)%=MOD;return *this;}
    mint_t operator*(const mint_t& a)const{mint_t res(*this);return res*=a;}
    mint_t fp(ll y)const{
        mint_t a=1,b=x;
        while(y){
            if(y&1)a*=b;
            b*=b;
            y/=2;
        }
        return a;
    }
    mint_t& operator/=(const mint_t& a){(*this)*=a.fp(MOD-2);return *this;}
    mint_t operator/(const mint_t& a)const{mint_t res(*this);return res/=a;}
};
#define mint mint_t<>
template<long long MOD>
istream& operator>>(istream& in, mint_t<MOD>& a){
    ll x;
    in>>x;
    a=mint_t<MOD>(x);
    return in;
}
template<long long MOD>
istream& operator<<(istream& out, mint_t<MOD>& a){
    out<<a.x;
    return out;
}
mint fct[FCTCST];
mint bnm(ll a,ll b){
    if(b>a || a<0)return 0;
    return fct[a]/fct[b]/fct[a-b];
}
ll n,m,k,a,b;
vi v;
bool bl[50007],bl2[50007];
vi g[50007];
ll dst[50007],dst2[50007],ds[50007];
const ll cns=4;
ll ds2[50007][cns+2],mn[50007];
ll ksz[50007],ksz2[100007],rs[50007];
ll ds3[50007][2];
void solve(){
    cin>>n>>m>>k;
    for(ll i=0;i<100007;i++)ksz2[i]=INF;
    for(ll i=0;i<m;i++){
      cin>>a>>b;
      g[a].pb(b);g[b].pb(a);
    }ll sm=0;
    for(ll i=0;i<n;i++){mn[i+1]=INF;
      char c;cin>>c;bl[i+1]=c-'0';sm+=c-'0';
      for(ll j=0;j<=cns;j++)ds2[i+1][j]=INF;
    }
    ll st;cin>>st;
    for(ll i=1;i<k;i++){
      cin>>a;v.pb(a);
    }
    for(ll i=1;i<=n;i++){
      for(ll j:g[i])if(bl[i]&&bl[j])bl2[i]=1;
     // cout<<bl[i]<<" "<<bl2[i]<<"\n";
    }
    queue<pii>q;
    for(ll i=1;i<=n;i++){
      if(bl[i])q.push({0,i});
    }
    while(q.size()){
      pii x=q.front();q.pop();
      if(dst[x.ss])continue;
      dst[x.ss]=x.ff;
      for(ll i:g[x.ss])q.push({x.ff+1,i});
    }
    deque<pii>pq;
    for(ll i=1;i<=n;i++){dst2[i]=-1;
      if(bl2[i])pq.pb({0,i});
    }
    while(pq.size()){
      pii x=pq.front();pq.pop_front();
      if(dst2[x.ss]!=-1)continue;
      dst2[x.ss]=x.ff;
      for(ll i:g[x.ss]){
        if(bl[x.ss])pq.push_front({x.ff,i});else pq.pb({x.ff+1,i});
      }
    }
    vii v2;
    // for(ll i=1;i<=n;i++){
    //   cout<<pii{dst[i]-2+(dst2[i]==0),dst2[i]}<<" ";
    // }cout<<endl;
    for(ll i : v){
      v2.pb({dst[i]-2+(dst2[i]==0),dst2[i]});
    }
    //cout<<v2;
    bl[st]=0;
    ll bs=INF;
    queue<ppi>q1,q2;
    q1.push({{0,0},st});
    while(q1.size() || q2.size()){
      if(q1.empty())swap(q1,q2);
      ppi x=q1.front();
     // cout<<x<<"\n";
      q1.pop();
      if(x.ff.ff<mn[x.ss])mn[x.ss]=x.ff.ff;
      if(x.ff.ff>=cns+mn[x.ss])continue;
      if(ds2[x.ss][x.ff.ff-mn[x.ss]]!=INF)continue;
      ds2[x.ss][x.ff.ff-mn[x.ss]]=x.ff.ss;
      for(ll i : g[x.ss]){
        if(bl[x.ss])q2.push({x.ff+pii{1,0},i});
        else q1.push({x.ff+pii{0,1},i});
      }
    }
    for(pii i:v2){

      ksz[1]+=i.ff+2;
      ksz[2]-=i.ff;
      if(i.ss!=-1)
      ksz[i.ss+1-i.ff]--;
    }
    ksz2[0]=0;
    for(ll i=1;i<=sm;i++){
      if(i!=1)ksz[i]+=ksz[i-1];
      ksz2[i]=ksz2[i-1]+ksz[i];
     // cout<<ksz[i]<<" ";
    }
    
    for(ll i=1;i<=n;i++){
     //  cout<<i<<": ";
     //  for(ll j=0;j<=min(cns,sm);j++)cout<<"{"<<mn[i]+j<<", "<<ds2[i][j]<<"}, ";cout<<"\n";
      ll bss=INFL;
      for(ll j=0;j<=min(cns,sm);j++)bss=min(bss,mn[i]+j+ds2[i][j]+ksz2[mn[i]+j]);
      rs[i]=bss;
    }
    if(k<=cns){
      ll aksm=ksz[1];
      for(ll i=2;i<=sm;i++){
        if(i==2 || ksz[i]!=ksz[i-1]){
          ll c=ksz[i]+1;
         // cout<<i<<" "<<c<<" ";
          ll c2=aksm-(i-1)*ksz[i];//cout<<c2<<"\n";
          for(ll j=1;j<=n;j++)ds3[j][0]=ds3[j][1]=INF;
          queue<ppi>q1,q2;
          q1.push({{0,0},st});
          while(q1.size() || q2.size()){
            if(q1.empty())swap(q1,q2);
            ppi x=q1.front();
            q1.pop();
            if(ds3[x.ss][x.ff.ss]!=INF)continue;
            //cout<<x<<"\n";
            ds3[x.ss][x.ff.ss]=x.ff.ff;
            if(x.ff.ss)
           rs[x.ss]=min(rs[x.ss],c2+x.ff.ff);
            for(ll i : g[x.ss]){
              if(bl[x.ss])q2.push({{x.ff.ff+c,1},i});
              else{
                while(q2.size() && ppi{x.ff+pii{1,0},i}>q2.front()){q1.push(q2.front());q2.pop();}
                q1.push({x.ff+pii{1,0},i});
              }
            }
          }
        }
        aksm+=ksz[i];
      }
    }
    for(ll i=1;i<=n;i++)cout<<rs[i]<<"\n";
  }
int main(){
    fct[0]=1;
    for(ll i=1;i<FCTCST;i++)fct[i]=fct[i-1]*i;
    ll t=1;
    //cin>>t;
    for(ll i=1;i<=t;i++){
        //cout<<"Case #"<<i<<": ";
        solve();
    }
}

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