답안 #919702

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
919702 2024-02-01T13:33:52 Z PieArmy Tracks in the Snow (BOI13_tracks) C++17
100 / 100
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

tracks.cpp: In function 'int main()':
tracks.cpp:83:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:83:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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