oj.uz

답안 #27485

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
27485 2017-07-13T07:22:42 Z TAMREF Tracks in the Snow (BOI13_tracks) C++11
91.25 / 100
 2000 ms 494544 KB 
#include <bits/stdc++.h>
#define val(r,c) ((F[r][(c)/16]&((unsigned int)3<<((c)%16*2)))>>((c)%16*2))
using namespace std;
const int mx=4002, ms=4000*4000+1;
vector<vector<int>> G(1,vector<int>());
//vector<int> G[ms];
int rep[ms];
unsigned int F[4000][256];
int ans=0, rt=1, d, n, m, g=1;
void bfs(){
    memset(rep,0,sizeof(rep));
    queue<int> node,dep;
    node.push(rt);
    dep.push(1);
    for(;!node.empty();){
        int now=node.front(), dnow=dep.front();
        node.pop(); dep.pop();
        if(rep[now]) continue;
        rep[now]=1; d=max(d,dnow);
        for(int u : G[now]){
            if(!rep[u]){
                node.push(u);
                dep.push(dnow+1);
            }
        }
    }
}
void input(){
    scanf("%d %d\n",&n,&m);
    int f;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            f=getchar();
            f=(f=='F'?0:(f=='R'?1:2));
            F[i][j/16]|=((unsigned int)f<<(j%16*2));
        }
        getchar();
    }
}
void gennode(){
    for(int now=0;now<n*m;++now){
        if(rep[now]|| val(now/m,now%m)==2) continue;
        //printf("%d %d\n",now/m+1,now%m+1);
        G.push_back(vector<int>());
        stack<int> Q;
        Q.push(now); rep[now]=g;
        int cvar=val(now/m,now%m),var,r;
        for(int p;!Q.empty();){
            p=Q.top(); Q.pop();
            //printf("%d\n",val(p/m,p%m));
            rep[p]=g;
            if(p%m<m-1){
                r=p+1;
                var=val(r/m,r%m);
                if(var==cvar && !rep[r]){
                    rep[r]=g;
                    Q.push(r);
                }
                else if(var!=2){
                    if(rep[r] && var!=cvar && (G[rep[r]].empty() || G[rep[r]].back()!=g)){
                        G[g].push_back(rep[r]);
                        G[rep[r]].push_back(g);
                    }
                }
            }
            if(p%m>0){
                r=p-1;
                var=val(r/m,r%m);
                if(var==cvar && !rep[r]){
                    rep[r]=g;
                    Q.push(r);
                }
                else if(var!=2){
                    if(rep[r] && var!=cvar && (G[rep[r]].empty() || G[rep[r]].back()!=g)){
                        G[g].push_back(rep[r]);
                        G[rep[r]].push_back(g);
                    }
                }
            }
            if(p/m<n-1){
                r=p+m;
                var=val(r/m,r%m);
                if(var==cvar && !rep[r]){
                    rep[r]=g;
                    Q.push(r);
                }
                else if(var!=2){
                    if(rep[r] && var!=cvar && (G[rep[r]].empty() || G[rep[r]].back()!=g)){
                        G[g].push_back(rep[r]);
                        G[rep[r]].push_back(g);
                    }
                }
            }
            if(p/m>0){
                r=p-m;
                var=val(r/m,r%m);
                if(var==cvar && !rep[r]){
                    rep[r]=g;
                    Q.push(r);
                }
                else if(var!=2){
                    if(rep[r] && var!=cvar && (G[rep[r]].empty() || G[rep[r]].back()!=g)){
                        G[g].push_back(rep[r]);
                        G[rep[r]].push_back(g);
                    }
                }
            }
        }
        ++g;
    }
}
int main(){
    input();
    gennode();
/*
    printf("%d\n",g);
    for(int i=1;i<g;i++,puts("")) for(int x : G[i]) printf("%d ",x);
*/
    bfs();
    printf("%d\n",d);
    return 0;
}

Compilation message

tracks.cpp: In function 'void input()':
tracks.cpp:29:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d\n",&n,&m);
                           ^

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 72060 KB Output is correct
2 Correct 6 ms 68528 KB Output is correct
3 Correct 6 ms 68528 KB Output is correct
4 Correct 13 ms 68828 KB Output is correct
5 Correct 9 ms 69012 KB Output is correct
6 Correct 9 ms 68528 KB Output is correct
7 Correct 3 ms 68528 KB Output is correct
8 Correct 3 ms 68528 KB Output is correct
9 Correct 9 ms 68528 KB Output is correct
10 Correct 13 ms 69012 KB Output is correct
11 Correct 3 ms 68660 KB Output is correct
12 Correct 26 ms 69408 KB Output is correct
13 Correct 9 ms 69012 KB Output is correct
14 Correct 19 ms 69012 KB Output is correct
15 Correct 36 ms 71924 KB Output is correct
16 Correct 49 ms 72060 KB Output is correct
17 Correct 36 ms 71920 KB Output is correct
18 Correct 16 ms 68828 KB Output is correct

Subtask #2
61.25 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 69008 KB Output is correct
2 Correct 183 ms 82000 KB Output is correct
3 Correct 1293 ms 175420 KB Output is correct
4 Correct 299 ms 82616 KB Output is correct
5 Execution timed out 2000 ms 494544 KB Execution timed out
6 Correct 1519 ms 124624 KB Output is correct
7 Correct 9 ms 69008 KB Output is correct
8 Correct 16 ms 69008 KB Output is correct
9 Correct 23 ms 69012 KB Output is correct
10 Correct 6 ms 68812 KB Output is correct
11 Correct 6 ms 68812 KB Output is correct
12 Correct 6 ms 69396 KB Output is correct
13 Correct 199 ms 82000 KB Output is correct
14 Correct 116 ms 75324 KB Output is correct
15 Correct 136 ms 81864 KB Output is correct
16 Correct 89 ms 75280 KB Output is correct
17 Correct 519 ms 97344 KB Output is correct
18 Correct 569 ms 121788 KB Output is correct
19 Correct 296 ms 82616 KB Output is correct
20 Correct 313 ms 95304 KB Output is correct
21 Correct 719 ms 122052 KB Output is correct
22 Execution timed out 2000 ms 494544 KB Execution timed out
23 Correct 956 ms 124808 KB Output is correct
24 Correct 1002 ms 175020 KB Output is correct
25 Execution timed out 2000 ms 281484 KB Execution timed out
26 Correct 1136 ms 93824 KB Output is correct
27 Correct 1199 ms 77188 KB Output is correct
28 Correct 1646 ms 124624 KB Output is correct
29 Correct 1466 ms 96540 KB Output is correct
30 Correct 1386 ms 84136 KB Output is correct
31 Execution timed out 2000 ms 181888 KB Execution timed out
32 Correct 1213 ms 82044 KB Output is correct