| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 919702 | 2024-02-01T13:33:52 Z | PieArmy | Tracks in the Snow (BOI13_tracks) | C++17 | 1227 ms | 317600 KB |
typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n';
const ll inf=2000000000000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}
void code(){
int n,m;cin>>n>>m;
vector<vector<int>>team(n,vector<int>(m,-1));
char arr[n][m];for(auto &a:arr)for(char &x:a)cin>>x;
queue<int>q;
int las=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(arr[i][j]=='.')continue;
if(team[i][j]!=-1)continue;
char tur=arr[i][j];
q.push(i*m+j);
team[i][j]=las;
while(q.size()){
int pos=q.front();
q.pop();
int x=pos/m,y=pos%m;
if(x+1!=n&&arr[x+1][y]==tur&&team[x+1][y]==-1){
team[x+1][y]=team[x][y];
q.push(pos+m);
}
if(x&&arr[x-1][y]==tur&&team[x-1][y]==-1){
team[x-1][y]=team[x][y];
q.push(pos-m);
}
if(y+1!=m&&arr[x][y+1]==tur&&team[x][y+1]==-1){
team[x][y+1]=team[x][y];
q.push(pos+1);
}
if(y&&arr[x][y-1]==tur&&team[x][y-1]==-1){
team[x][y-1]=team[x][y];
q.push(pos-1);
}
}
las++;
}
}
vector<vector<int>>komsu(las,vector<int>(0));
for(int i=0;i<n;i++){
for(int j=0;j<m-1;j++){
if(arr[i][j]=='.'||arr[i][j+1]=='.'||team[i][j]==team[i][j+1])continue;
komsu[team[i][j]].pb(team[i][j+1]);
komsu[team[i][j+1]].pb(team[i][j]);
}
}
for(int i=0;i<n-1;i++){
for(int j=0;j<m;j++){
if(arr[i][j]=='.'||arr[i+1][j]=='.'||team[i][j]==team[i+1][j])continue;
komsu[team[i][j]].pb(team[i+1][j]);
komsu[team[i+1][j]].pb(team[i][j]);
}
}
int ans=0;
vector<int>vis(las,0);
vis[team[0][0]]=1;
q.push(team[0][0]);
while(q.size()){
int pos=q.front();
q.pop();
ans=vis[pos];
for(int x:komsu[pos]){
if(vis[x])continue;
vis[x]=vis[pos]+1;
q.push(x);
}
}
cout<<ans;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
int t=1;
if(!t)cin>>t;
while(t--){code();cout<<endl;}
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 23 ms | 5976 KB | Output is correct |
| 2 | Correct | 1 ms | 344 KB | Output is correct |
| 3 | Correct | 1 ms | 600 KB | Output is correct |
| 4 | Correct | 8 ms | 1884 KB | Output is correct |
| 5 | Correct | 4 ms | 1368 KB | Output is correct |
| 6 | Correct | 0 ms | 344 KB | Output is correct |
| 7 | Correct | 0 ms | 348 KB | Output is correct |
| 8 | Correct | 1 ms | 344 KB | Output is correct |
| 9 | Correct | 1 ms | 344 KB | Output is correct |
| 10 | Correct | 4 ms | 1372 KB | Output is correct |
| 11 | Correct | 2 ms | 604 KB | Output is correct |
| 12 | Correct | 8 ms | 2392 KB | Output is correct |
| 13 | Correct | 4 ms | 1368 KB | Output is correct |
| 14 | Correct | 4 ms | 1372 KB | Output is correct |
| 15 | Correct | 19 ms | 5212 KB | Output is correct |
| 16 | Correct | 25 ms | 5980 KB | Output is correct |
| 17 | Correct | 15 ms | 4184 KB | Output is correct |
| 18 | Correct | 7 ms | 1880 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 1112 KB | Output is correct |
| 2 | Correct | 87 ms | 24144 KB | Output is correct |
| 3 | Correct | 539 ms | 189996 KB | Output is correct |
| 4 | Correct | 131 ms | 37712 KB | Output is correct |
| 5 | Correct | 576 ms | 317600 KB | Output is correct |
| 6 | Correct | 868 ms | 165488 KB | Output is correct |
| 7 | Correct | 2 ms | 1112 KB | Output is correct |
| 8 | Correct | 2 ms | 1112 KB | Output is correct |
| 9 | Correct | 3 ms | 1112 KB | Output is correct |
| 10 | Correct | 1 ms | 604 KB | Output is correct |
| 11 | Correct | 2 ms | 856 KB | Output is correct |
| 12 | Correct | 2 ms | 1112 KB | Output is correct |
| 13 | Correct | 83 ms | 23988 KB | Output is correct |
| 14 | Correct | 46 ms | 14212 KB | Output is correct |
| 15 | Correct | 43 ms | 14672 KB | Output is correct |
| 16 | Correct | 39 ms | 11344 KB | Output is correct |
| 17 | Correct | 233 ms | 62112 KB | Output is correct |
| 18 | Correct | 197 ms | 56148 KB | Output is correct |
| 19 | Correct | 140 ms | 37664 KB | Output is correct |
| 20 | Correct | 124 ms | 42616 KB | Output is correct |
| 21 | Correct | 325 ms | 111952 KB | Output is correct |
| 22 | Correct | 598 ms | 317148 KB | Output is correct |
| 23 | Correct | 450 ms | 118608 KB | Output is correct |
| 24 | Correct | 339 ms | 141596 KB | Output is correct |
| 25 | Correct | 1076 ms | 228260 KB | Output is correct |
| 26 | Correct | 473 ms | 72404 KB | Output is correct |
| 27 | Correct | 581 ms | 98192 KB | Output is correct |
| 28 | Correct | 882 ms | 165424 KB | Output is correct |
| 29 | Correct | 801 ms | 152968 KB | Output is correct |
| 30 | Correct | 737 ms | 133236 KB | Output is correct |
| 31 | Correct | 1227 ms | 232532 KB | Output is correct |
| 32 | Correct | 527 ms | 104872 KB | Output is correct |