Submission #101640

#	Time	Username	Problem	Language	Result	Execution time	Memory
101640		SomeoneUnknown	Tracks in the Snow (BOI13_tracks)	C++14	50.73 / 100	2092 ms	276340 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;
typedef pair<int, ii> iii;

ii mii(int b, int c){
    return make_pair(b,c);
}

iii miii(int a, int b, int c){
    return make_pair(a, mii(b,c));
}

int main(){
    //ios_base::sync_with_stdio(false);
    int r, c;
    //cin >> r >> c;
    scanf("%d %d", &r, &c);
    //string m[r];
    char m[r][c+2];
    bool written[r][c+2];
    for(int i = 0; i < r; i++){
        //cin >> m[i];
        //cout << "read";
        scanf("%s", &m[i]);
        //for(int j = 0; j < c; j++) written[i][j] = false;
    }
    priority_queue<ii> vable[r+c];
    vable[0].push(mii(0, 0));
    vable[0].push(mii(r-1, c-1));
    //written[0][0] = written[r-1][c-1] = true;
    int most = 0;
    for(int que = 0; que < r+c; que++){
    while(!vable[que].empty()){
        ii ving = vable[que].top();
        vable[que].pop();
        int y = ving.first;
        int x = ving.second;
        if(m[y][x] == '.') continue;
        most = max(most, que);
        if(y != r-1){
            vable[que+(m[y][x]!=m[y+1][x])].push(mii(y+1, x));
        }
        if(x != c-1){
            vable[que+(m[y][x]!=m[y][x+1])].push(mii(y, x+1));
        }
        if(y != 0){
            vable[que+(m[y][x]!=m[y-1][x])].push(mii(y-1, x));
        }
        if(x != 0){
            vable[que+(m[y][x]!=m[y][x-1])].push(mii(y, x-1));
        }
        m[y][x] = '.';
    }
    }
    printf("%d", most+1);//*/
}
/*
5 8
FFRF....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
*/

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:26:26: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[(c + 2)]' [-Wformat=]
         scanf("%s", &m[i]);
                     ~~~~~^
tracks.cpp:22:10: warning: unused variable 'written' [-Wunused-variable]
     bool written[r][c+2];
          ^~~~~~~
tracks.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &r, &c);
     ~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", &m[i]);
         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 26.666666666666668 / 30
• Subtask 2: 24.0625 / 70