oj.uz

답안 #1094332

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1094332 2024-09-29T10:44:03 Z MattNattFeczan Tracks in the Snow (BOI13_tracks) C++14
78.125 / 100
 1928 ms 1048576 KB 
#include<bits/stdc++.h>
#include <bitset>
using namespace std;

const int N = 4000;
string S[2];
vector<pair<int,int>>Graf1[N*N]; //czy rozne kolory, wierzcholek
int idx[N*N], c=1;
bitset<N*N> c1, c2;
vector<int>Graf[N*N];

void DFS1(int n, int v){
  c1[n] = c, idx[n] = v;
  for(auto& elm : Graf1[n]){
    if(c1[elm.second] == 0 && elm.first == 0){
      DFS1(elm.second, v);
    }
  }
}

int makeTree(int n, int m){
  int v = 0, d = 0;
  for(int i=0;i<n*m;i++){
    if(c1[i] == 0)
      DFS1(i, v++);
  }
  for(int i=0;i<n*m;i++){
    for(auto& elm : Graf1[i]){
      if(idx[elm.second] != idx[i])
        Graf[idx[i]].push_back(idx[elm.second]);
    }
    Graf1[i].clear();
  }
  queue<pair<int,int>>Q;
  Q.push({0, 1});
  while(!Q.empty()){
    auto now = Q.front();
    Q.pop();
    if(c2[now.first] == c)
      continue;
    c2[now.first] = c, d = max(d, now.second);
    for(auto& elm : Graf[now.first]){
      if(c2[elm] != c){
        Q.push({elm, now.second+1});
      }
    }
  }
  return d;
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n,m;
  cin>>n>>m;
  for(int i=0;i<n;i++){
    S[0] = S[1];
    cin>>S[1];
    for(int j=0;j<m;j++){
      if(S[1][j] == '.')
        continue;
      if(i != 0){
        if(S[0][j] == S[1][j]){
          Graf1[i*m+j].push_back({0, (i-1)*m+j}), Graf1[(i-1)*m+j].push_back({0, i*m+j});
        }
        else if(S[0][j] != '.'){
          Graf1[i*m+j].push_back({1, (i-1)*m+j}), Graf1[(i-1)*m+j].push_back({1, i*m+j});
        }
      }
      if(j != 0){
        if(S[1][j-1] == S[1][j]){
          Graf1[i*m+j-1].push_back({0, i*m+j}), Graf1[i*m+j].push_back({0, i*m+j-1});
        }
        else if(S[1][j-1] != '.'){
          Graf1[i*m+j-1].push_back({1, i*m+j}), Graf1[i*m+j].push_back({1, i*m+j-1});
        }
      }
    }
  }
  cout<<makeTree(n, m)<<"\n";
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 323 ms 767112 KB Output is correct
2 Correct 290 ms 751916 KB Output is correct
3 Correct 280 ms 751952 KB Output is correct
4 Correct 326 ms 761704 KB Output is correct
5 Correct 318 ms 753256 KB Output is correct
6 Correct 310 ms 751940 KB Output is correct
7 Correct 304 ms 751956 KB Output is correct
8 Correct 305 ms 752208 KB Output is correct
9 Correct 313 ms 751968 KB Output is correct
10 Correct 313 ms 753748 KB Output is correct
11 Correct 330 ms 754516 KB Output is correct
12 Correct 323 ms 757132 KB Output is correct
13 Correct 313 ms 753240 KB Output is correct
14 Correct 335 ms 753236 KB Output is correct
15 Correct 352 ms 763728 KB Output is correct
16 Correct 358 ms 767056 KB Output is correct
17 Correct 336 ms 758864 KB Output is correct
18 Correct 341 ms 761680 KB Output is correct

Subtask #2
48.125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 322 ms 752724 KB Output is correct
2 Correct 461 ms 797008 KB Output is correct
3 Correct 1064 ms 1040468 KB Output is correct
4 Correct 502 ms 800000 KB Output is correct
5 Runtime error 806 ms 1048576 KB Execution killed with signal 9
6 Runtime error 975 ms 1048576 KB Execution killed with signal 9
7 Correct 319 ms 752756 KB Output is correct
8 Correct 301 ms 752976 KB Output is correct
9 Correct 306 ms 754004 KB Output is correct
10 Correct 326 ms 752468 KB Output is correct
11 Correct 320 ms 752612 KB Output is correct
12 Correct 301 ms 752612 KB Output is correct
13 Correct 451 ms 796872 KB Output is correct
14 Correct 383 ms 778236 KB Output is correct
15 Correct 425 ms 770388 KB Output is correct
16 Correct 385 ms 775508 KB Output is correct
17 Correct 695 ms 866144 KB Output is correct
18 Correct 667 ms 824672 KB Output is correct
19 Correct 540 ms 800080 KB Output is correct
20 Correct 490 ms 818004 KB Output is correct
21 Correct 800 ms 922704 KB Output is correct
22 Runtime error 801 ms 1048576 KB Execution killed with signal 9
23 Correct 967 ms 975952 KB Output is correct
24 Correct 720 ms 939060 KB Output is correct
25 Correct 1928 ms 1048288 KB Output is correct
26 Runtime error 790 ms 1048576 KB Execution killed with signal 9
27 Runtime error 769 ms 1048576 KB Execution killed with signal 9
28 Runtime error 743 ms 1048576 KB Execution killed with signal 9
29 Runtime error 751 ms 1048576 KB Execution killed with signal 9
30 Runtime error 776 ms 1048576 KB Execution killed with signal 9
31 Runtime error 834 ms 1048576 KB Execution killed with signal 9
32 Runtime error 812 ms 1048576 KB Execution killed with signal 9