oj.uz

답안 #1107968

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1107968 2024-11-02T13:29:06 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++14
21.5625 / 100
 875 ms 430152 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 46 ms 37448 KB Execution killed with signal 8
2 Correct 1 ms 2640 KB Output is correct
3 Correct 1 ms 2640 KB Output is correct
4 Correct 10 ms 17656 KB Output is correct
5 Runtime error 26 ms 23632 KB Execution killed with signal 8
6 Correct 1 ms 2640 KB Output is correct
7 Correct 2 ms 2640 KB Output is correct
8 Correct 2 ms 2640 KB Output is correct
9 Correct 2 ms 4832 KB Output is correct
10 Runtime error 21 ms 19180 KB Execution killed with signal 8
11 Correct 4 ms 9040 KB Output is correct
12 Runtime error 34 ms 23716 KB Execution killed with signal 11
13 Runtime error 25 ms 23632 KB Execution killed with signal 8
14 Runtime error 27 ms 23632 KB Execution killed with signal 8
15 Runtime error 41 ms 37572 KB Execution killed with signal 8
16 Runtime error 46 ms 37464 KB Execution killed with signal 8
17 Runtime error 42 ms 37448 KB Execution killed with signal 11
18 Correct 11 ms 17744 KB Output is correct

Subtask #2
6.5625 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 180 ms 248676 KB Execution killed with signal 8
2 Runtime error 114 ms 97864 KB Execution killed with signal 8
3 Runtime error 560 ms 357192 KB Execution killed with signal 8
4 Runtime error 168 ms 142716 KB Execution killed with signal 11
5 Runtime error 603 ms 430060 KB Execution killed with signal 8
6 Runtime error 809 ms 313672 KB Execution killed with signal 11
7 Runtime error 163 ms 256840 KB Execution killed with signal 8
8 Runtime error 155 ms 248440 KB Execution killed with signal 8
9 Runtime error 13 ms 6748 KB Execution killed with signal 8
10 Correct 3 ms 3164 KB Output is correct
11 Correct 13 ms 124360 KB Output is correct
12 Runtime error 17 ms 15196 KB Execution killed with signal 8
13 Runtime error 106 ms 98300 KB Execution killed with signal 8
14 Runtime error 71 ms 67652 KB Execution killed with signal 8
15 Runtime error 91 ms 77640 KB Execution killed with signal 11
16 Runtime error 55 ms 37192 KB Execution killed with signal 8
17 Runtime error 227 ms 163680 KB Execution killed with signal 11
18 Runtime error 247 ms 165700 KB Execution killed with signal 11
19 Runtime error 194 ms 143948 KB Execution killed with signal 11
20 Runtime error 169 ms 137800 KB Execution killed with signal 8
21 Runtime error 397 ms 264992 KB Execution killed with signal 8
22 Runtime error 653 ms 430152 KB Execution killed with signal 8
23 Runtime error 365 ms 230728 KB Execution killed with signal 8
24 Runtime error 451 ms 296168 KB Execution killed with signal 8
25 Runtime error 745 ms 405252 KB Execution killed with signal 8
26 Correct 423 ms 130120 KB Output is correct
27 Runtime error 672 ms 288848 KB Execution killed with signal 8
28 Runtime error 875 ms 319980 KB Execution killed with signal 11
29 Runtime error 835 ms 303440 KB Execution killed with signal 8
30 Runtime error 747 ms 293716 KB Execution killed with signal 11
31 Runtime error 757 ms 291412 KB Execution killed with signal 8
32 Runtime error 679 ms 294740 KB Execution killed with signal 11