oj.uz

Submission #27486

# Submission time Handle Problem Language Result Execution time Memory
27486 2017-07-13T07:24:00 Z TAMREF Tracks in the Snow (BOI13_tracks) C++11
0 / 100
 2000 ms 583944 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<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);
        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(){
    //freopen("input.txt","rt",stdin);
    input();
    gennode();
/*
    printf("%d\n",g);
    for(int i=1;i<g;i++,puts("")) for(int x : G[i]) printf("%d ",x);
*/
  	assert(0);
    bfs();
    printf("%d\n",d);
    return 0;
}

Compilation message

tracks.cpp: In function 'void input()':
tracks.cpp:28: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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 444808 KB Execution killed because of forbidden syscall gettid (186)
2 Runtime error 76 ms 443528 KB Execution killed because of forbidden syscall gettid (186)
3 Runtime error 39 ms 443528 KB Execution killed because of forbidden syscall gettid (186)
4 Runtime error 69 ms 443656 KB Execution killed because of forbidden syscall gettid (186)
5 Runtime error 53 ms 443784 KB Execution killed because of forbidden syscall gettid (186)
6 Runtime error 36 ms 443528 KB Execution killed because of forbidden syscall gettid (186)
7 Runtime error 49 ms 443528 KB Execution killed because of forbidden syscall gettid (186)
8 Runtime error 16 ms 443528 KB Execution killed because of forbidden syscall gettid (186)
9 Runtime error 43 ms 443528 KB Execution killed because of forbidden syscall gettid (186)
10 Runtime error 49 ms 443784 KB Execution killed because of forbidden syscall gettid (186)
11 Runtime error 33 ms 443528 KB Execution killed because of forbidden syscall gettid (186)
12 Runtime error 66 ms 444040 KB Execution killed because of forbidden syscall gettid (186)
13 Runtime error 43 ms 443784 KB Execution killed because of forbidden syscall gettid (186)
14 Runtime error 39 ms 443784 KB Execution killed because of forbidden syscall gettid (186)
15 Runtime error 73 ms 444808 KB Execution killed because of forbidden syscall gettid (186)
16 Runtime error 69 ms 444808 KB Execution killed because of forbidden syscall gettid (186)
17 Runtime error 83 ms 444680 KB Execution killed because of forbidden syscall gettid (186)
18 Runtime error 49 ms 443656 KB Execution killed because of forbidden syscall gettid (186)

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 443656 KB Execution killed because of forbidden syscall gettid (186)
2 Runtime error 233 ms 449800 KB Execution killed because of forbidden syscall gettid (186)
3 Runtime error 1133 ms 489096 KB Execution killed because of forbidden syscall gettid (186)
4 Runtime error 283 ms 451464 KB Execution killed because of forbidden syscall gettid (186)
5 Execution timed out 2000 ms 583944 KB Execution timed out
6 Runtime error 1606 ms 463148 KB Execution killed because of forbidden syscall gettid (186)
7 Runtime error 29 ms 443656 KB Execution killed because of forbidden syscall gettid (186)
8 Runtime error 36 ms 443656 KB Execution killed because of forbidden syscall gettid (186)
9 Runtime error 36 ms 443784 KB Execution killed because of forbidden syscall gettid (186)
10 Runtime error 49 ms 443656 KB Execution killed because of forbidden syscall gettid (186)
11 Runtime error 49 ms 443656 KB Execution killed because of forbidden syscall gettid (186)
12 Runtime error 49 ms 443912 KB Execution killed because of forbidden syscall gettid (186)
13 Runtime error 216 ms 449800 KB Execution killed because of forbidden syscall gettid (186)
14 Runtime error 136 ms 447244 KB Execution killed because of forbidden syscall gettid (186)
15 Runtime error 159 ms 448008 KB Execution killed because of forbidden syscall gettid (186)
16 Runtime error 119 ms 446472 KB Execution killed because of forbidden syscall gettid (186)
17 Runtime error 469 ms 459912 KB Execution killed because of forbidden syscall gettid (186)
18 Runtime error 423 ms 460808 KB Execution killed because of forbidden syscall gettid (186)
19 Runtime error 263 ms 451464 KB Execution killed because of forbidden syscall gettid (186)
20 Runtime error 333 ms 453896 KB Execution killed because of forbidden syscall gettid (186)
21 Runtime error 729 ms 470664 KB Execution killed because of forbidden syscall gettid (186)
22 Execution timed out 2000 ms 583944 KB Execution timed out
23 Runtime error 836 ms 475152 KB Execution killed because of forbidden syscall gettid (186)
24 Runtime error 1049 ms 490248 KB Execution killed because of forbidden syscall gettid (186)
25 Runtime error 1759 ms 514696 KB Execution killed because of forbidden syscall gettid (186)
26 Runtime error 1149 ms 468856 KB Execution killed because of forbidden syscall gettid (186)
27 Runtime error 1226 ms 452184 KB Execution killed because of forbidden syscall gettid (186)
28 Runtime error 1496 ms 463148 KB Execution killed because of forbidden syscall gettid (186)
29 Runtime error 1353 ms 455304 KB Execution killed because of forbidden syscall gettid (186)
30 Runtime error 1353 ms 451800 KB Execution killed because of forbidden syscall gettid (186)
31 Runtime error 1859 ms 494984 KB Execution killed because of forbidden syscall gettid (186)
32 Runtime error 1093 ms 453784 KB Execution killed because of forbidden syscall gettid (186)