oj.uz

Submission #1066303

# Submission time Handle Problem Language Result Execution time Memory
1066303 2024-08-19T17:37:53 Z NemanjaSo2005 Board Game (JOI24_boardgame) C++17
17 / 100
 1188 ms 7324 KB 
#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];
 //  cout<<"UNEO INPUT"<<endl;
}
void BFS(){
   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;
    //  cout<<tren<<" "<<d<<endl;
      if(dist[tren]!=1e18)
         continue;
      dist[tren]=d;
      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<=N;i++)
      if(stop[i])
         Q.push({i,0});
   BFS();
   for(int i=1;i<=N;i++)
      d1[i]=dist[i];
   for(int i=1;i<=N;i++){
      if(d1[i]==0){
         if(nexttostop[i])
            d1[i]=1;
         else
            d1[i]=2;
      }
   }/*
   for(int i=1;i<=N;i++)
      cout<<d1[i]<<" ";
   cout<<endl;*/
   //cout<<"OVDE"<<endl;
   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<=100;i++)
         cena[i]+=min(d1[x]+2*(i-1),d2[x]+(i-1));
   }
   for(int i=100;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<=100;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;
}
/*
15 15 2
1 2
1 10
2 3
3 4
4 5
5 6
6 7
7 8
7 10
8 9
10 11
11 12
12 13
13 14
14 15
000000111100000
1 15
*/

Compilation message

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++)
      |                ~^~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3676 KB Output is correct
2 Correct 11 ms 5064 KB Output is correct
3 Correct 17 ms 5976 KB Output is correct
4 Correct 15 ms 5708 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3672 KB Output is correct
2 Correct 566 ms 5212 KB Output is correct
3 Correct 469 ms 6740 KB Output is correct
4 Correct 461 ms 6996 KB Output is correct
5 Correct 1044 ms 7172 KB Output is correct
6 Correct 1036 ms 6740 KB Output is correct
7 Correct 528 ms 6228 KB Output is correct
8 Correct 444 ms 6620 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3672 KB Output is correct
2 Correct 597 ms 5208 KB Output is correct
3 Correct 1016 ms 6608 KB Output is correct
4 Correct 493 ms 6868 KB Output is correct
5 Correct 516 ms 7324 KB Output is correct
6 Correct 991 ms 6740 KB Output is correct
7 Correct 1044 ms 6604 KB Output is correct
8 Correct 566 ms 7252 KB Output is correct
9 Correct 1188 ms 6812 KB Output is correct
10 Correct 1180 ms 6744 KB Output is correct

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3672 KB Output is correct
2 Correct 52 ms 3672 KB Output is correct
3 Correct 29 ms 3672 KB Output is correct
4 Incorrect 69 ms 3828 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 5980 KB Output is correct
2 Incorrect 66 ms 6976 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 5980 KB Output is correct
2 Incorrect 66 ms 6976 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3672 KB Output is correct
2 Correct 52 ms 3672 KB Output is correct
3 Correct 29 ms 3672 KB Output is correct
4 Incorrect 69 ms 3828 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3676 KB Output is correct
2 Correct 11 ms 5064 KB Output is correct
3 Correct 17 ms 5976 KB Output is correct
4 Correct 15 ms 5708 KB Output is correct
5 Correct 43 ms 3672 KB Output is correct
6 Correct 566 ms 5212 KB Output is correct
7 Correct 469 ms 6740 KB Output is correct
8 Correct 461 ms 6996 KB Output is correct
9 Correct 1044 ms 7172 KB Output is correct
10 Correct 1036 ms 6740 KB Output is correct
11 Correct 528 ms 6228 KB Output is correct
12 Correct 444 ms 6620 KB Output is correct
13 Correct 26 ms 3672 KB Output is correct
14 Correct 597 ms 5208 KB Output is correct
15 Correct 1016 ms 6608 KB Output is correct
16 Correct 493 ms 6868 KB Output is correct
17 Correct 516 ms 7324 KB Output is correct
18 Correct 991 ms 6740 KB Output is correct
19 Correct 1044 ms 6604 KB Output is correct
20 Correct 566 ms 7252 KB Output is correct
21 Correct 1188 ms 6812 KB Output is correct
22 Correct 1180 ms 6744 KB Output is correct
23 Correct 53 ms 3672 KB Output is correct
24 Correct 52 ms 3672 KB Output is correct
25 Correct 29 ms 3672 KB Output is correct
26 Incorrect 69 ms 3828 KB Output isn't correct
27 Halted 0 ms 0 KB -