Submission #1176369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176369		achinhchin	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	1097 ms	33064 KiB

jobs

#include <climits>
#include <cstring>
#include<iostream>
#include<utility>
#include<vector>
#include<queue>
using namespace std;
typedef long long l;
using pl=pair<l,l>;
#define f first
#define s second
l n,m,i,j,md,ll,r=INT_MAX,T[900][900],B[900][900],w[][2]={{0,1},{0,-1},{1,0},{-1,0}};
vector<pl> G[900][900];
queue<pl> D;
char M[900][900];
pl a,b,t;
char ti;

bool C(l tm) {
  memset(T,0,900*900*8),T[a.f][a.s]=tm*m+1,D.push(a);
  while(!D.empty()){
    t=D.front(),D.pop();
    for(auto i:G[t.f][t.s])if(!T[i.f][i.s]&&(T[t.f][t.s]-1)/m<B[i.f][i.s])
      D.push(make_pair(i.f,i.s)),T[i.f][i.s]=T[t.f][t.s]+1;
  }return T[b.f][b.s];
}

int main(){
  //cin.tie(nullptr)->sync_with_stdio(false);
  cin>>n>>m;
  for(i=1;i<=n;i++)for(j=1;j<=n;j++){cin>>ti,M[i][j]=ti;
    if (ti=='M')a.f=i,a.s=j,M[i][j]='G';
    if(ti=='G'){
      if(M[i-1][j]=='G'||M[i-1][j]=='H'){if (M[i-1][j]!='H')G[i][j].emplace_back(i-1,j);G[i-1][j].emplace_back(i,j);}
      if(M[i][j-1]=='G'||M[i][j-1]=='H'){if (M[i][j-1]!='H')G[i][j].emplace_back(i,j-1);G[i][j-1].emplace_back(i,j);}
    }else if(ti=='H') {
      if(M[i-1][j]=='G')G[i][j].emplace_back(i-1,j);
      if(M[i][j-1]=='G')G[i][j].emplace_back(i,j-1);
      D.push(make_pair(i,j));
    }else if(ti=='D')b.f=i,b.s=j;
  }while(!D.empty()){
    t=D.front(),D.pop();for(auto i:G[t.f][t.s])if(!B[i.f][i.s])D.push(make_pair(i.f,i.s)),B[i.f][i.s]=B[t.f][t.s]+1;
  }for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(!B[i][j])B[i][j]=LONG_LONG_MAX;
  for(auto i:w)if(M[b.f+i[0]][b.s+i[1]]=='G')G[b.f+i[0]][b.s+i[1]].emplace_back(b.f,b.s);
  while (ll!=r)md=(ll+r)/2,C(md)?ll=md+1:r=md; cout<<ll-1;
}

• Subtask 1: 0 / 100