oj.uz

Submission #248671

# Submission time Handle Problem Language Result Execution time Memory
248671 2020-07-13T04:48:36 Z Marlov Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 19 ms 20608 KB 
/*
Code by @marlov       
*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <iterator>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

#define maxV 30005

int N,M;
pair<int,int> doge[maxV];
map< int,map<int,bool> > visited;
//bool visited[maxV][maxV];
queue<int> cnts[maxV];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    for(int i=0;i<M;i++){
        cin>>doge[i].first>>doge[i].second;
        cnts[doge[i].first].push(i);
    }
    //bfs
    queue< pair< int,pair<int,int> > > q;
    q.push(make_pair(0,make_pair(0,doge[0].first)));
    visited[0][doge[0].first]=true;
    while(!q.empty()){
        int cd=q.front().first;
        int ci=q.front().second.first;
        int cl=q.front().second.second;
        q.pop();
        //solution
        if(ci==1){
            cout<<cd<<'\n';
            return 0;
        }
        while(!cnts[cl].empty()){
            q.push(make_pair(cd,make_pair(cnts[cl].front(),cl)));
            cnts[cl].pop();
        }
        if(cl-doge[ci].second>=0&&visited[ci][cl-doge[ci].second]==false){
            q.push(make_pair(cd+1,make_pair(ci,cl-doge[ci].second)));
            visited[ci][cl-doge[ci].second]=true;
        }
        if(cl+doge[ci].second<N&&visited[ci][cl+doge[ci].second]==false){
            q.push(make_pair(cd+1,make_pair(ci,cl+doge[ci].second)));
            visited[ci][cl+doge[ci].second]=true;
        }

    }
    cout<<"-1"<<'\n';
    return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1,n=0?)
	* do smth instead of nothing and stay organized
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 20480 KB Output is correct
2 Correct 14 ms 20480 KB Output is correct
3 Correct 14 ms 20480 KB Output is correct
4 Correct 19 ms 20480 KB Output is correct
5 Correct 14 ms 20480 KB Output is correct
6 Correct 15 ms 20480 KB Output is correct
7 Correct 14 ms 20480 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20480 KB Output is correct
2 Correct 15 ms 20480 KB Output is correct
3 Correct 15 ms 20480 KB Output is correct
4 Correct 14 ms 20480 KB Output is correct
5 Correct 14 ms 20480 KB Output is correct
6 Correct 14 ms 20480 KB Output is correct
7 Correct 14 ms 20480 KB Output is correct
8 Correct 14 ms 20480 KB Output is correct
9 Incorrect 14 ms 20480 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 20480 KB Output is correct
2 Correct 15 ms 20480 KB Output is correct
3 Correct 14 ms 20480 KB Output is correct
4 Correct 13 ms 20480 KB Output is correct
5 Correct 14 ms 20480 KB Output is correct
6 Correct 14 ms 20480 KB Output is correct
7 Correct 14 ms 20480 KB Output is correct
8 Correct 14 ms 20480 KB Output is correct
9 Incorrect 14 ms 20480 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 20480 KB Output is correct
2 Correct 14 ms 20480 KB Output is correct
3 Correct 17 ms 20524 KB Output is correct
4 Correct 14 ms 20480 KB Output is correct
5 Correct 14 ms 20480 KB Output is correct
6 Correct 14 ms 20480 KB Output is correct
7 Correct 14 ms 20480 KB Output is correct
8 Correct 14 ms 20480 KB Output is correct
9 Incorrect 14 ms 20480 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 20480 KB Output is correct
2 Correct 14 ms 20592 KB Output is correct
3 Correct 14 ms 20608 KB Output is correct
4 Correct 14 ms 20480 KB Output is correct
5 Correct 14 ms 20480 KB Output is correct
6 Correct 14 ms 20480 KB Output is correct
7 Correct 14 ms 20480 KB Output is correct
8 Correct 16 ms 20608 KB Output is correct
9 Incorrect 14 ms 20480 KB Output isn't correct
10 Halted 0 ms 0 KB -