Submission #60474

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
60474	2018-07-24T08:40:03 Z	istlemin	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	1000 ms	18228 KB

skyscraper

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

int main(){
	cin.sync_with_stdio(false);
    ll n,m;
    cin>>n>>m;

    vi b(m);
    vi p(m);

    rep(i,0,m) cin>>b[i]>>p[i];

    set<tuple<ll,ll> > q; //(jumps,doge);
    q.emplace(0,0);

    vector<bool> seen(m);

    while(q.size()){
        ll doge,jumps;
        tie(jumps,doge) = *q.begin();
        q.erase(q.begin());

		if(seen[doge]) continue;
		seen[doge] = true;

        if(doge==1){
            cout<<jumps<<endl;
            return 0;
        }

        rep(i,0,m){
            if((b[i]-b[doge])%p[doge]==0)
				q.emplace(jumps+abs(b[i]-b[doge])/p[doge],i);
        }
    }

    cout<<-1<<endl;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	252 KB	Output is correct
2	Correct	3 ms	544 KB	Output is correct
3	Correct	3 ms	544 KB	Output is correct
4	Correct	3 ms	544 KB	Output is correct
5	Correct	4 ms	544 KB	Output is correct
6	Correct	3 ms	544 KB	Output is correct
7	Correct	3 ms	544 KB	Output is correct

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	576 KB	Output is correct
2	Correct	3 ms	576 KB	Output is correct
3	Correct	3 ms	580 KB	Output is correct
4	Correct	3 ms	584 KB	Output is correct
5	Correct	3 ms	588 KB	Output is correct
6	Correct	4 ms	592 KB	Output is correct
7	Correct	3 ms	600 KB	Output is correct
8	Correct	3 ms	600 KB	Output is correct
9	Correct	0 ms	604 KB	Output is correct
10	Correct	5 ms	612 KB	Output is correct
11	Correct	4 ms	612 KB	Output is correct
12	Correct	5 ms	912 KB	Output is correct
13	Correct	717 ms	1164 KB	Output is correct
14	Correct	105 ms	1588 KB	Output is correct
15	Correct	108 ms	1664 KB	Output is correct

Subtask #3

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1664 KB	Output is correct
2	Correct	3 ms	1664 KB	Output is correct
3	Correct	3 ms	1664 KB	Output is correct
4	Correct	3 ms	1664 KB	Output is correct
5	Correct	3 ms	1664 KB	Output is correct
6	Correct	4 ms	1664 KB	Output is correct
7	Correct	2 ms	1664 KB	Output is correct
8	Correct	4 ms	1664 KB	Output is correct
9	Correct	2 ms	1664 KB	Output is correct
10	Correct	4 ms	1664 KB	Output is correct
11	Correct	4 ms	1664 KB	Output is correct
12	Correct	3 ms	1664 KB	Output is correct
13	Correct	610 ms	1664 KB	Output is correct
14	Correct	90 ms	1752 KB	Output is correct
15	Correct	90 ms	1760 KB	Output is correct
16	Correct	3 ms	1760 KB	Output is correct
17	Correct	46 ms	2424 KB	Output is correct
18	Correct	3 ms	2424 KB	Output is correct
19	Correct	3 ms	2424 KB	Output is correct
20	Execution timed out	1076 ms	14492 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #4

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	14492 KB	Output is correct
2	Correct	3 ms	14492 KB	Output is correct
3	Correct	3 ms	14492 KB	Output is correct
4	Correct	3 ms	14492 KB	Output is correct
5	Correct	3 ms	14492 KB	Output is correct
6	Correct	3 ms	14492 KB	Output is correct
7	Correct	3 ms	14492 KB	Output is correct
8	Correct	3 ms	14492 KB	Output is correct
9	Correct	3 ms	14492 KB	Output is correct
10	Correct	4 ms	14492 KB	Output is correct
11	Correct	4 ms	14492 KB	Output is correct
12	Correct	5 ms	14492 KB	Output is correct
13	Correct	767 ms	14492 KB	Output is correct
14	Correct	87 ms	14492 KB	Output is correct
15	Correct	97 ms	14492 KB	Output is correct
16	Correct	3 ms	14492 KB	Output is correct
17	Correct	49 ms	14492 KB	Output is correct
18	Correct	4 ms	14492 KB	Output is correct
19	Correct	3 ms	14492 KB	Output is correct
20	Execution timed out	1065 ms	17648 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #5

0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	17648 KB	Output is correct
2	Correct	3 ms	17648 KB	Output is correct
3	Correct	3 ms	17648 KB	Output is correct
4	Correct	2 ms	17648 KB	Output is correct
5	Correct	2 ms	17648 KB	Output is correct
6	Correct	3 ms	17648 KB	Output is correct
7	Correct	3 ms	17648 KB	Output is correct
8	Correct	2 ms	17648 KB	Output is correct
9	Correct	3 ms	17648 KB	Output is correct
10	Correct	5 ms	17648 KB	Output is correct
11	Correct	3 ms	17648 KB	Output is correct
12	Correct	4 ms	17648 KB	Output is correct
13	Correct	734 ms	17648 KB	Output is correct
14	Correct	111 ms	17648 KB	Output is correct
15	Correct	94 ms	17648 KB	Output is correct
16	Correct	3 ms	17648 KB	Output is correct
17	Correct	43 ms	17648 KB	Output is correct
18	Correct	4 ms	17648 KB	Output is correct
19	Correct	3 ms	17648 KB	Output is correct
20	Execution timed out	1077 ms	18228 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-