Submission #1066272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066272		NemanjaSo2005	Board Game (JOI24_boardgame)	C++17	3 / 100	4086 ms	7004 KiB

Main

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=5e4+5;
vector<int> graf[maxn];
ll N,M,K,poz[maxn],res[maxn],dist[maxn],d1[maxn],d2[maxn],cena[maxn],propval[maxn];
bool nexttostop[maxn];
int prosli[maxn],pvred;
string stop;
priority_queue<pair<ll,ll>> PQ;
queue<pair<int,int>> Q;
void input(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cin>>N>>M>>K;
   while(M--){
      int a,b;
      cin>>a>>b;
      graf[a].push_back(b);
      graf[b].push_back(a);
   }
   cin>>stop;
   stop="0"+stop+"0000";
   for(int i=0;i<stop.size();i++)
      stop[i]-='0';
   for(int i=1;i<=K;i++)
      cin>>poz[i];
}
void BFS(bool props=true){
   for(int i=1;i<=N;i++)
      dist[i]=1e18;
   while(Q.size()){
      auto x=Q.front();
      Q.pop();
      int tren=x.first;
      int d=x.second;
      if(dist[tren]!=1e18)
         continue;
      dist[tren]=d;
      if(stop[tren] and props==false)
         continue;
      for(int y:graf[tren])
         Q.push({y,d+1});
   }
}
void solve1(){
   int poc=poz[1];
   Q.push({poc,0});
   BFS();
   for(int i=1;i<=N;i++)
      cout<<dist[i]<<"\n";
}
void calcdist(){
   for(int i=1;i<=N;i++){
      nexttostop[i]=false;
      for(int x:graf[i])
         nexttostop[i]|=stop[x];
   }
   for(int i=1;i<=K;i++){
      int poc=poz[i];
      d1[poc]=1e18;
      Q.push({poc,0});
      BFS();
      for(int j=1;j<=N;j++)
         if(stop[j]==1)
            d1[poc]=min(d1[poc],dist[j]);
      if(d1[poc]==0)
         if(nexttostop[poc])
            d1[poc]=1;
         else
            d1[poc]=2;
   }

   for(int i=1;i<=N;i++)
      d2[i]=1e18;
   for(int i=1;i<=N;i++)
      if(nexttostop[i] and stop[i])
         PQ.push({-1,i});
   pvred++;
   while(PQ.size()){
      auto aa=PQ.top();
      PQ.pop();
      int tren=aa.second;
      int d=-aa.first;
      if(prosli[tren]==pvred)
         continue;
      prosli[tren]=pvred;
      d2[tren]=d;
      for(int x:graf[tren])
         PQ.push({-(d+1-stop[tren]),x});
   }

}
void calcchange(){
   for(int i=2;i<=K;i++){
      int x=poz[i];
      for(int i=1;i<=N;i++)
         cena[i]+=min(d1[x]+2*(i-1),d2[x]+(i-1));
   }
   for(int i=N;i>=2;i--)
      cena[i]-=cena[i-1];
}
void Dijkstra(){
   pvred++;
   while(PQ.size()){
      auto aa=PQ.top();
      PQ.pop();
      int tren=aa.second;
      ll d=-aa.first;
      if(prosli[tren]==pvred)
         continue;
     // cout<<tren<<" "<<d<<endl;
      prosli[tren]=pvred;
      dist[tren]=min(dist[tren],d);
      if(stop[tren] and propval[tren]!=d)
         continue;
      for(int x:graf[tren])
         PQ.push({-(d+1),x});
   }
}
int main(){
   input();
   bool hasstop=false;
   for(int i=1;i<=N;i++)
      if(stop[i])
         hasstop=true;
   if(hasstop==false){
      solve1();
      return 0;
   }

   calcdist();
  // cout<<"AAA"<<endl;
   calcchange();
   //cout<<"BB"<<endl;

  /* cout<<"CENE"<<endl;
   for(int i=1;i<=N;i++)
      cout<<cena[i]<<" ";
   cout<<endl;
*/
   for(int i=1;i<=N;i++)
      dist[i]=res[i]=1e18;
   int poc=poz[1];
   //dist[poc]=res[poc]=0;
   for(int i=1;i<=N;i++)
      propval[i]=-1;
   propval[poc]=0;
   PQ.push({0,poc});
   Dijkstra();

  /* for(int i=1;i<=N;i++)
      cout<<dist[i]<<" ";
   cout<<endl;
*/
   for(int i=1;i<=N;i++)
      res[i]=min(dist[i],res[i]);

   for(int it=1;it<=N;it++){
      for(int i=1;i<=N;i++)
         propval[i]=-1;
      for(int i=1;i<=N;i++)
         if(stop[i] and dist[i]<1e17){
            ll d=dist[i]+cena[it];
            PQ.push({-d,i});
            propval[i]=d;
         }
      for(int i=1;i<=N;i++)
         dist[i]=1e18;
      Dijkstra();
      for(int i=1;i<=N;i++)
         res[i]=min(dist[i],res[i]);
   }
   for(int i=1;i<=N;i++)
      cout<<res[i]<<"\n";
   return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void input()':
Main.cpp:24:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |    for(int i=0;i<stop.size();i++)
      |                ~^~~~~~~~~~~~
Main.cpp: In function 'void calcdist()':
Main.cpp:67:9: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   67 |       if(d1[poc]==0)
      |         ^

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