oj.uz

Submission #123998

# Submission time Handle Problem Language Result Execution time Memory
123998 2019-07-02T10:36:46 Z Mtaylor Bali Sculptures (APIO15_sculpture) C++17
0 / 100
 22 ms 23800 KB 
#include <bits/stdc++.h>
 
    using namespace std;
    typedef long long ll;
    typedef vector<ll> vl ;
 
    #define mp make_pair
    #define pb push_back
    #define f first
    #define s second
    #define all(v) (v).begin(),(v).end()
 
 
    const int MOD = 1000000007;
    const int N = 1000005;
    const double PI =4*atan(1);
    const double eps = 1e-7;
 
    ll n,m;
    ll x,y;
    vl tab[N];
    ll p[N];
    ll b[N];
    bool vis[N];
    unordered_map<ll ,ll> maa;
    set <pair<ll,ll>> sss;
    ll ans=-1;
 
    void bfs(ll u){
      priority_queue<pair<ll,ll> > pq;
		for(auto t:tab[u]){
			pq.push(mp(0,u*50000 + p[t]));
		}
		vis[u]=1;
      pair<ll,ll>  ras;
      while(!pq.empty()){
        ras=pq.top();
        pq.pop();
        ll x=ras.s/50000;
        ll y=ras.s%50000;
        if(x==b[1]){
          ans=-ras.f;
          return ;
        }
        //cout << x << " " << y << endl;
        if(x+y <n && maa[50000*(x+y)+y]==0){
        	maa[50000*(x+y)+y]=1;
        	if(x+y == b[1]){
        		ans=ras.f-1;
        		return;
        	}
        	pq.push(mp(ras.f-1,50000*(x+y)+y));
        }
        if(x-y >=0 && maa[50000*(x-y)+y]==0){
        	maa[50000*(x-y)+y]=1;
        	if(x-y == b[1]){
        		ans=ras.f-1;
        		return;
        	}
        	pq.push(mp(ras.f-1,50000*(x-y)+y));
        }
        //cout << x << endl;
        if(vis[x])continue;
        for(auto t: tab[x]){
        	if(maa[x*50000+p[t]]==0)
          pq.push(mp(ras.f,x*50000+p[t] ));
          maa[x*50000+p[t]]=1;
        }
        vis[x]=1;
      }
    }
 
 
   
 
    int main(){
        ios::sync_with_stdio(0);
        //freopen("easy.txt","r",stdin);
        cin >> n >>m ;
        for(int i=0;i<m;i++){
          cin >> x >> y;
          p[i]=y;
          b[i]=x;
          tab[x].pb(i);
        }
        //cout << b[0]<< endl;
        bfs(b[0]);
        cout << -ans;
 
 
 
 
        return 0;
    }

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -