oj.uz

Submission #361456

# Submission time Handle Problem Language Result Execution time Memory
361456 2021-01-30T09:10:57 Z alireza_kaviani Jakarta Skyscrapers (APIO15_skyscraper) C++11
22 / 100
 94 ms 114924 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)						(x).begin(),(x).end()
#define X							first
#define Y							second
#define sep							' '
#define endl						'\n'
#define SZ(x)						ll(x.size())

const ll MAXN = 1e4 + 10;
const ll SQ = 200;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

int n , m , ptr , q[MAXN * SQ * 4] , dist[MAXN * SQ * 2];
vector<int> adj[MAXN * SQ * 2];

void BFS(int v){
	fill(dist , dist + MAXN * SQ * 2 , MOD);
	dist[v] = 0;
	int ql = MAXN * SQ * 2 , qr = ql;
	q[qr++] = v;
	while(ql < qr){
		int v = q[ql++];
		for(int u : adj[v]){
			int cost = (v >= n + m && u >= n + m);
			if(dist[u] > dist[v] + cost){
				dist[u] = dist[v] + cost;
				if(cost == 0)	q[--ql] = u;
				else	q[qr++] = u;
			}
		}
	}
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> n >> m;
	ptr = n + m;
	assert(n <= 2000);
	for(int i = 1 ; i < SQ ; i++){
		for(int j = 0 ; j + i < n ; j++){
			adj[ptr + j].push_back(ptr + j + i);
			adj[ptr + j + i].push_back(ptr + j);
		}
		for(int j = 0 ; j < n ; j++){
			adj[ptr + j].push_back(j);
		}
		ptr += n;
	}
	for(int i = 0 ; i < m ; i++){
		int x , y;
		cin >> x >> y;
		adj[x].push_back(n + i);
		if(y < SQ){
			adj[n + i].push_back(m + n * y + x);
			continue;
		}
		int z = x % y;
		for(int j = z ; j + y < n ; j += y){
			adj[ptr].push_back(ptr + 1);
			adj[ptr + 1].push_back(ptr);
			if(j == x){
				adj[n + i].push_back(ptr);
			}
			ptr++;
		}
		if(adj[n + i].size() == 0)	adj[n + i].push_back(ptr);
		ptr++;
	}
	BFS(n);
	/*for(int i = 0 ; i < ptr ; i++){
		cout << i << sep << dist[i] << endl;
	}*/
	cout << (dist[n + 1] == MOD ? -1 : dist[n + 1]) << endl;

    return 0;
}
/*

*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 110060 KB Output is correct
2 Correct 74 ms 110060 KB Output is correct
3 Correct 75 ms 110060 KB Output is correct
4 Correct 79 ms 110188 KB Output is correct
5 Correct 74 ms 110056 KB Output is correct
6 Correct 74 ms 110060 KB Output is correct
7 Correct 75 ms 110060 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 110060 KB Output is correct
2 Correct 78 ms 110060 KB Output is correct
3 Correct 76 ms 110060 KB Output is correct
4 Correct 83 ms 110060 KB Output is correct
5 Correct 75 ms 110060 KB Output is correct
6 Correct 74 ms 110060 KB Output is correct
7 Correct 75 ms 110060 KB Output is correct
8 Correct 76 ms 110316 KB Output is correct
9 Correct 79 ms 110444 KB Output is correct
10 Correct 80 ms 110828 KB Output is correct
11 Correct 76 ms 110828 KB Output is correct
12 Correct 77 ms 110700 KB Output is correct
13 Correct 76 ms 110700 KB Output is correct
14 Correct 76 ms 110828 KB Output is correct
15 Correct 77 ms 110828 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 110188 KB Output is correct
2 Correct 76 ms 110060 KB Output is correct
3 Correct 74 ms 110060 KB Output is correct
4 Correct 74 ms 110060 KB Output is correct
5 Correct 81 ms 110060 KB Output is correct
6 Correct 76 ms 110236 KB Output is correct
7 Correct 75 ms 110188 KB Output is correct
8 Correct 74 ms 110316 KB Output is correct
9 Correct 75 ms 110572 KB Output is correct
10 Correct 84 ms 110828 KB Output is correct
11 Correct 78 ms 110828 KB Output is correct
12 Correct 78 ms 110700 KB Output is correct
13 Correct 80 ms 110700 KB Output is correct
14 Correct 76 ms 110828 KB Output is correct
15 Correct 76 ms 110828 KB Output is correct
16 Correct 88 ms 111340 KB Output is correct
17 Incorrect 93 ms 114924 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 110060 KB Output is correct
2 Correct 73 ms 110060 KB Output is correct
3 Correct 74 ms 110060 KB Output is correct
4 Correct 74 ms 110188 KB Output is correct
5 Correct 76 ms 110152 KB Output is correct
6 Correct 76 ms 110060 KB Output is correct
7 Correct 75 ms 110060 KB Output is correct
8 Correct 75 ms 110316 KB Output is correct
9 Correct 75 ms 110572 KB Output is correct
10 Correct 84 ms 110828 KB Output is correct
11 Correct 77 ms 110828 KB Output is correct
12 Correct 76 ms 110700 KB Output is correct
13 Correct 77 ms 110700 KB Output is correct
14 Correct 79 ms 110828 KB Output is correct
15 Correct 77 ms 110828 KB Output is correct
16 Correct 88 ms 111340 KB Output is correct
17 Incorrect 94 ms 114924 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 110060 KB Output is correct
2 Correct 74 ms 110060 KB Output is correct
3 Correct 74 ms 110168 KB Output is correct
4 Correct 76 ms 110060 KB Output is correct
5 Correct 75 ms 110060 KB Output is correct
6 Correct 75 ms 110060 KB Output is correct
7 Correct 75 ms 110188 KB Output is correct
8 Correct 75 ms 110316 KB Output is correct
9 Correct 75 ms 110444 KB Output is correct
10 Correct 75 ms 110700 KB Output is correct
11 Correct 77 ms 110828 KB Output is correct
12 Correct 76 ms 110700 KB Output is correct
13 Correct 77 ms 110828 KB Output is correct
14 Correct 79 ms 110828 KB Output is correct
15 Correct 76 ms 110828 KB Output is correct
16 Correct 77 ms 111340 KB Output is correct
17 Incorrect 93 ms 114924 KB Output isn't correct
18 Halted 0 ms 0 KB -