Submission #582958

#TimeUsernameProblemLanguageResultExecution timeMemory
582958Justin1Jakarta Skyscrapers (APIO15_skyscraper)C++14
10 / 100
68 ms101504 KiB
#include <bits/stdc++.h> #define f first #define s second using namespace std; using pii = pair<int,int>; struct edge{ int v, c; }; const int maxpow = 2000; int n,m,k,x,y,z; int pos[4002005], power[4002005]; vector<edge> gph[4002005]; int dis[4002005]; priority_queue<pii,vector<pii>,greater<pii>> nxt; int f(int i, int j) { //2d to 1d return (i-1)*maxpow+j; } string g(int i) { if (i > n*n) cout << i-maxpow*n; else cout << "(" << i/maxpow+1 << "," << i%maxpow << ")"; return ""; } void dijkstra() { for (int i = 1; i <= n*maxpow+n; i++) dis[i] = -1; nxt.push({0,f(pos[1],power[1])}); while (nxt.size()) { auto tmp = nxt.top(); nxt.pop(); if (dis[tmp.s] != -1) continue; // cout << g(tmp.s) << " (" << tmp.f << ")\n"; dis[tmp.s] = tmp.f; for (auto i : gph[tmp.s]) nxt.push({tmp.f+i.c,i.v}); } cout << dis[n*n+pos[2]] << '\n'; } int main() { cin >> n >> m; for (int i = 1; i <= m; i++) cin >> pos[i] >> power[i]; for (int i = 1; i <= m; i++) pos[i]++; for (int i = 1; i <= maxpow; i++) { //pow for (int j = 1; j <= i; j++) { for (int l = j; l+i <= n; l += i) { //pos gph[f(l,i)].push_back({f(l+i,i),1}); gph[f(l+i,i)].push_back({f(l,i),1}); } } for (int j = 1; j <= n; j++) gph[f(j,i)].push_back({n*n+j,0}); } for (int i = 1; i <= m; i++) gph[n*n+pos[i]].push_back({f(pos[i],power[i]),0}); dijkstra(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...