oj.uz

답안 #1107969

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1107969 2024-11-02T13:29:22 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++11
21.5625 / 100
 951 ms 425556 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 1e5 +5, inf = INT_MAX, LL = 30;
 
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
int comp[4005][4005];
unordered_map<int,int> edg[4005];
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};
void rush(){
    int n,m;
    cin>>n>>m;
 
    vector<vector<char>> arr(n,vector<char>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            comp[i][j]=-1;
            cin>>arr[i][j];
        }
    }
 
    int ct = 0;
    int u,v,a,b;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(arr[i][j]!='.' && comp[i][j]==-1){
                queue<pair<int,int>> q;
                q.push({i,j});
                comp[i][j]=ct;
                while(!q.empty()){
 
                    pair<int,int> node = q.front();q.pop();
                    for(int x=0;x<4;x++){
                        a = node.first + dx[x];
                        b =  node.second + dy[x];
                        if(a>=0 && a<n && b>=0 && b<m && comp[a][b]==-1 && arr[a][b]==arr[i][j]){
                            comp[a][b]=ct;
                            q.push({a,b});
                        }
                    }
 
                }
                ct++;
            }
        }
    }
    vector<int> graph[ct];
    for(int i =0;i<n;i++){
        for(int j=0;j<m;j++){
            if(comp[i][j]!=-1){
 
                for(int x= 0; x<4;x++){
                    a = i + dx[x];
                    b = j + dy[x];
                    if(a>=0 && a<n && b>=0 && b<m && comp[a][b] !=-1 && comp[a][b]!=comp[i][j]){
                        u = min(comp[i][j],comp[a][b]);
                        v =max(comp[i][j],comp[a][b]);
                        if(edg[u][v]==0 ){
                            edg[u][v]=1;
                            graph[u].pb(v);
                            graph[v].pb(u);
                        }
                    }
                }
 
            }
        }
    }
    int ans=0;
    queue<pair<int,int>> q;
    vector<int> used(ct,0);
    q.push({0,1});
    used[0]=1;
    while(!q.empty()){
        auto node = q.front();
        ans=max(ans,node.second);
        q.pop();
        for(auto v:graph[node.first]){
        if(!used[v]){
                used[v]=1;
                q.push({v,node.second+1});
            }
        }
    }
    putr(ans);
}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1; 
    // cin>>tt;
 
    while(tt--){
        rush();
    }
 
    return 0;
}

Subtask #1
15.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 42 ms 37468 KB Execution killed with signal 8
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 10 ms 17500 KB Output is correct
5 Runtime error 23 ms 23460 KB Execution killed with signal 8
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Runtime error 20 ms 19292 KB Execution killed with signal 8
11 Correct 6 ms 9064 KB Output is correct
12 Runtime error 31 ms 23896 KB Execution killed with signal 11
13 Runtime error 32 ms 23640 KB Execution killed with signal 8
14 Runtime error 25 ms 23632 KB Execution killed with signal 8
15 Runtime error 42 ms 37656 KB Execution killed with signal 8
16 Runtime error 53 ms 37608 KB Execution killed with signal 8
17 Runtime error 42 ms 37448 KB Execution killed with signal 11
18 Correct 11 ms 17488 KB Output is correct

Subtask #2
6.5625 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 167 ms 248392 KB Execution killed with signal 8
2 Runtime error 115 ms 97864 KB Execution killed with signal 8
3 Runtime error 551 ms 357192 KB Execution killed with signal 8
4 Runtime error 172 ms 142152 KB Execution killed with signal 11
5 Runtime error 668 ms 425556 KB Execution killed with signal 8
6 Runtime error 951 ms 313684 KB Execution killed with signal 11
7 Runtime error 185 ms 256596 KB Execution killed with signal 8
8 Runtime error 175 ms 248244 KB Execution killed with signal 8
9 Runtime error 14 ms 6736 KB Execution killed with signal 8
10 Correct 2 ms 3168 KB Output is correct
11 Correct 16 ms 124176 KB Output is correct
12 Runtime error 18 ms 15208 KB Execution killed with signal 8
13 Runtime error 117 ms 98396 KB Execution killed with signal 8
14 Runtime error 87 ms 67668 KB Execution killed with signal 8
15 Runtime error 88 ms 77596 KB Execution killed with signal 11
16 Runtime error 51 ms 36948 KB Execution killed with signal 8
17 Runtime error 220 ms 163760 KB Execution killed with signal 11
18 Runtime error 227 ms 165508 KB Execution killed with signal 11
19 Runtime error 188 ms 143684 KB Execution killed with signal 11
20 Runtime error 158 ms 137032 KB Execution killed with signal 8
21 Runtime error 352 ms 263528 KB Execution killed with signal 8
22 Runtime error 611 ms 425544 KB Execution killed with signal 8
23 Runtime error 443 ms 226716 KB Execution killed with signal 8
24 Runtime error 391 ms 296264 KB Execution killed with signal 8
25 Runtime error 711 ms 397128 KB Execution killed with signal 8
26 Correct 456 ms 127012 KB Output is correct
27 Runtime error 708 ms 288900 KB Execution killed with signal 8
28 Runtime error 931 ms 313668 KB Execution killed with signal 11
29 Runtime error 905 ms 303456 KB Execution killed with signal 8
30 Runtime error 793 ms 293716 KB Execution killed with signal 11
31 Runtime error 750 ms 291668 KB Execution killed with signal 8
32 Runtime error 565 ms 294768 KB Execution killed with signal 11