Submission #625138

#TimeUsernameProblemLanguageResultExecution timeMemory
625138StavabTracks in the Snow (BOI13_tracks)C++14
47.50 / 100
2099 ms156960 KiB
#include <iostream> #include <vector> using namespace std; vector<vector<char>> field; int h, w, prints = 0; vector<int> father, chainSize; int find(int n) { if(father[n] != n) father[n] = find(father[n]); return father[n]; } void join(int a, int b) { a = find(a); b = find(b); if(a == b) return; if(chainSize[a] < chainSize[b]) swap(a, b); father[b] = a; chainSize[a] += chainSize[b]; } int animals(char curPrint) { if(chainSize[find(0)] == prints) return 1; int cur = find(0); for(int i = 0; i < h; i++) { for(int j = 0; j < w; j++) { if(field[i][j] != curPrint) continue; if(i != 0) { if(find((i - 1)*w + j) == cur) join(i*w + j, 0); } if(j != 0) { if(find(i*w + j - 1) == cur) join(i*w + j, 0); } if(i != h - 1) { if(find((i + 1)*w + j) == cur) join(i*w + j, 0); } if(j != w - 1) { if(find(i*w + j + 1) == cur) join(i*w + j, 0); } } } if(curPrint == 'R') return animals('F') + 1; return animals('R') + 1; } int main() { scanf("%d %d", &h, &w); field.assign(h, vector<char>(w)); father.assign(h*w, 0); chainSize.assign(h*w, 1); for(int i = 0; i < h; i++) { for(int j = 0; j < w; j++) { scanf(" %c", &field[i][j]); father[i*w + j] = i*w + j; if(field[i][j] == '.') continue; prints++; if(i != 0) { if(field[i - 1][j] == field[i][j]) join(i*w + j, (i - 1)*w + j); } if(j != 0) { if(field[i][j - 1] == field[i][j]) join(i*w + j, i*w + j - 1); } } } if(field[0][0] == 'F') printf("%d\n", animals('R')); else printf("%d\n", animals('F')); return 0; }

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     scanf("%d %d", &h, &w);
      |     ~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:86:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |             scanf(" %c", &field[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...