//https://oj.uz/problem/view/APIO15_skyscraper
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
#define pii pair<int,int>
int n,m;
int root;
//position / power
struct E{
int pos;
int pow;
int waga;
};
struct Node{
int d;
int pos;
int pow;
};
class comp{
public:
bool operator()(Node A,Node B){
return A.d<B.d;
}
};
vector<pair<int,int>> kand,doges;
unordered_map<int,bool> odw[30009];
vector<E> edges[30001][174];
int dis[30001][174];
void build(){
for(int i=0;i<n;i++){
for(int j=1;j<=root;j++){
edges[i][j].pb({i,0,0});
}
}
}
void addsmaller(int pos,int pow){
if(odw[pow][pos%pow]) return;
else odw[pow][pos%pow] = 1;
int pos2 = pos;
while(pos2+pow<n){
edges[pos2][pow].pb({pos2+pow,pow,1});
edges[pos2+pow][pow].pb({pos2,pow,1});
pos2 += pow;
}
pos2 = pos;
while(pos2-pow>=0){
edges[pos2][pow].pb({pos2-pow,pow,1});
edges[pos2-pow][pow].pb({pos2,pow,1});
pos2 -= pow;
}
}
void addbigger(int pos,int pow){
int pos2 = pos;
int dl = 1;
while(pos2+pow<n){
edges[pos][0].pb({pos2+pow,0,dl});
pos2 += pow;
dl++;
}
pos2 = pos;
dl = 1;
while(pos2-pow>=0){
edges[pos][0].pb({pos2-pow,0,dl});
pos2 -= pow;
dl++;
}
}
priority_queue<Node,vector<Node>,comp> q;
void dijkstra(int pocz){
q.push({0,pocz,0});
while(!q.empty()){
auto t = q.top();
q.pop();
t.d = -t.d;
if(dis[t.pos][t.pow] != t.d)
continue;
for(auto x:edges[t.pos][t.pow]){
if(t.d + x.waga < dis[x.pos][x.pow]){
dis[x.pos][x.pow] = t.d + x.waga;
q.push({-dis[x.pos][x.pow],x.pos,x.pow});
}
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>m;
root = (int)sqrt(n);
build();
int zero,one;
for(int i=0;i<m;i++){
int pos,pow;
cin>>pos>>pow;
kand.pb({pos,pow});
if(i>1) continue;
if(i == 0){
zero = pos;
} else if(i == 1){
one = pos;
}
}
sort(kand.begin(),kand.end());
doges.pb(kand[0]);
for(int i=1;i<m;i++){
if(kand[i-1] != kand[i])
doges.pb(kand[i]);
}
for(int i=0;i<doges.size();i++){
int pos = doges[i].st;
int pow = doges[i].nd;
if(pow <= root){
edges[pos][0].pb({pos,pow,0});
addsmaller(pos,pow);
} else if(pow<=n){
addbigger(pos,pow);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<=root;j++){
dis[i][j] = 1000000000;
}
}
dis[zero][0] = 0;
dijkstra(zero);
pair<long long,pii> maxi = {0,{0,0}};
int s = 0;
for(int i=0;i<n;i++){
for(int j=0;j<=root;j++){
s += edges[i][j].size();
if(edges[i][j].size()>maxi.st)
maxi = {(long long)edges[i][j].size(),{i,j}};
//cout<<"pos: "<<i<<" pow: "<<j<<endl;
//for(auto x:edges[i][j]){
//cout<<"pos: "<<x.pos<<" pow: "<<x.pow<<" waga: "<<x.waga<<endl;
//}
}
}
cout<<s<<" "<<maxi.st<<" "<<maxi.nd.st<<" "<<maxi.nd.nd<<endl;
if(dis[one][0] == 1000000000){
cout<<"-1\n";
} else cout<<dis[one][0]<<endl;
return 0;
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i=0;i<doges.size();i++){
| ~^~~~~~~~~~~~~
skyscraper.cpp:134:34: warning: comparison of integer expressions of different signedness: 'std::vector<E>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
134 | if(edges[i][j].size()>maxi.st)
| ^
skyscraper.cpp:144:18: warning: 'one' may be used uninitialized in this function [-Wmaybe-uninitialized]
144 | if(dis[one][0] == 1000000000){
| ~~~~~~~~~~^
skyscraper.cpp:127:13: warning: 'zero' may be used uninitialized in this function [-Wmaybe-uninitialized]
127 | dijkstra(zero);
| ~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
124436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
124484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
124516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
124480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
124492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
