Submission #14911

#	Time	Username	Problem	Language	Result	Execution time	Memory
14911		ainta	Palembang Bridges (APIO15_bridge)	C++98	0 / 100	0 ms	135708 KiB

bridge

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<map>
#define N_ 7600000
using namespace std;
int n, m, Num[N_], D[N_], Q1[N_], Q2[N_];
vector<int>E[30100];
map<int,int>Map;
bool be[N_], ed[N_];
struct A{
    int a, b;
}w[30100];
int cnt;
void Make(int a, int b, int x){
    int i;
    be[cnt+1]=true;
    for(i=b;i<n;i+=a){
        ++cnt;
        Num[cnt] = i;
        if(x == i) E[x].push_back(cnt);
    }
    ed[cnt] = true;
}
void BFS(int a){
    int i, h=0,t=0,tt=0, x;
    for(i=0;i<=cnt;i++)D[i]=999999999;
    D[a]=0;
    Q1[++t] = a;
    while(t){
        while(h<t){
            x=Q1[++h];
            if(x<n){
                for(i=0;i<E[x].size();i++){
                    if(D[E[x][i]] > D[x]){
                        D[E[x][i]]=D[x];
                        Q1[++t] = E[x][i];
                    }
                }
            }
            else{
                if(D[Num[x]] > D[x]){
                    D[Num[x]] = D[x];
                    Q1[++t] = Num[x];
                }
            }
        }
        tt = 0;
        for(i=1;i<=t;i++){
            if(Q1[i]<n)continue;
            x=Q1[i];
            if(!be[x] && D[x-1] >D[x]+1){
                D[x-1]=D[x]+1;
                Q2[++tt] = x-1;
            }
            if(!ed[x] && D[x+1] > D[x]+1){
                D[x+1]=D[x]+1;
                Q2[++tt] = x+1;
            }
        }
        for(i=1;i<=tt;i++)Q1[i]=Q2[i];
        t=tt;
        h=0;
    }
}
int main(){
    int i, p1, p2, t;
    scanf("%d%d",&n,&m);
    cnt = n;
    for(i=1;i<=m;i++){
        scanf("%d%d",&w[i].a,&w[i].b);
        t = w[i].b*30100+(w[i].a%w[i].b);
        if(!Map[t]){
            Map[t]=cnt + 1;
            Make(w[i].b, w[i].a%w[i].b, w[i].a);
        }
        else{
            E[w[i].a].push_back(Map[t] + w[i].a/w[i].b);
        }
    }
    p1 = w[1].a, p2 = w[2].a;
    BFS(p1);
    printf("%d\n",D[p2]==999999999?-1:D[p2]);
}

Compilation message (stderr)

bridge.cpp: In function 'void BFS(int)':
bridge.cpp:34:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(i=0;i<E[x].size();i++){
                          ^
bridge.cpp: In function 'int main()':
bridge.cpp:68:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
bridge.cpp:71:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&w[i].a,&w[i].b);
                                      ^

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37