Submission #1044760

#TimeUsernameProblemLanguageResultExecution timeMemory
1044760YassineBenYounesSky Walking (IOI19_walk)C++17
0 / 100
4061 ms122540 KiB
#include<bits/stdc++.h> #include<chrono> #include<random> typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef double db; ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD) ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM) int dx[8] = {1, 0, 0, -1, 1, 1, -1, -1}; int dy[8] = {0, 1, -1, 0, 1, -1, -1, 1}; #define endl "\n" #define ss second #define ff first #define all(x) (x).begin() , (x).end() #define pb push_back #define vi vector<int> #define vii vector<pair<int,int>> #define vl vector<ll> #define vll vector<pair<ll,ll>> #define pii pair<int,int> #define pll pair<ll,ll> #define pdd pair<double,double> #define vdd vector<pdd> #define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define pbds tree<pii, null_type, less<pii>,rb_tree_tag, tree_order_statistics_node_update> using namespace __gnu_pbds; using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ////////////////////Only Clear Code////////////////////////// void usaco_problem(){ freopen("milkvisits.in", "r", stdin); freopen("milkvisits.out", "w", stdout); } void init(){ #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // ONLINE_JUDGE } const int mx = 2e5+5; const int LOG = 22; const int inf = 1e9; const ll mod = 1e9+7; const int sq = 320; #include "walk.h" int n, m; vii graph[mx]; ll distances[mx]; bool vis[mx]; ll min_distance(vi x,vi h,vi l,vi r,vi y,int s, int g){ n = x.size(), m = y.size(); map<pii, int> ind; vii points = {{x[s], 0}, {x[g], 0}}; int cnt = 0; distances[cnt] = 1e18; vis[cnt] = 0; ind[{x[s], 0}] = cnt++; distances[cnt] = 1e18; vis[cnt] = 0; ind[{x[g], 0}] = cnt++; for(int j = 0; j < m;j++){ for(int i = 0;i < n;i++){ if(h[i] >= y[j] && l[j] <= i && i <= r[j]){ points.pb({x[i], y[j]}); distances[cnt] = 1e18; vis[cnt] = 0; //cout << x[i] << " " << y[j] << " " << cnt << endl; ind[{x[i], y[j]}] = cnt++; } } } sort(all(points)); /*for(pii p : points){ cout << p.ff << " " << p.ss << endl; }*/ for(int i = 0; i < n;i++){ vii v; for(pii a : points){ if(a.ff == x[i])v.pb({ind[a], a.ss}); } for(int j = 0;j < v.size()-1;j++){ graph[v[j].ff].pb({v[j+1].ff, v[j+1].ss - v[j].ss}); graph[v[j+1].ff].pb({v[j].ff, v[j+1].ss - v[j].ss}); } } for(int i = 0; i < m;i++){ vii v; for(pii a : points){ if(a.ss == y[i] && a.ff >= x[l[i]] && a.ff <= x[r[i]])v.pb({ind[a], a.ff}); } for(int j = 0;j < v.size()-1;j++){ graph[v[j].ff].pb({v[j+1].ff, v[j+1].ss - v[j].ss}); graph[v[j+1].ff].pb({v[j].ff, v[j+1].ss - v[j].ss}); } } distances[0] = 0; priority_queue<pll, vector<pll>, greater<pll>> pq; pq.push({0, 0}); while(!pq.empty()){ int node = pq.top().ss; ll dis = pq.top().ff; pq.pop(); if(vis[node])continue; vis[node] = 1; for(pii adj : graph[node]){ ll nw = dis + adj.ss; if(nw < distances[adj.ff]){ distances[adj.ff] = nw; pq.push({distances[adj.ff], adj.ff}); } } } return distances[1]; } /* int32_t main(){ init(); speed; cout << min_distance({0, 4, 5, 6, 9}, {6, 6, 6, 6, 6}, {3, 1, 0}, {4, 3, 2}, {1, 3, 6}, 0, 4) << endl; }*/ /* NEVER GIVE UP! DOING SMTHNG IS BETTER THAN DOING NTHNG!!! Your Guide when stuck: - Continue keyword only after reading the whole input - Don't use memset with testcases - Check for corner cases(n=1, n=0) - Check where you declare n(Be careful of declaring it globally and in main) */

Compilation message (stderr)

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:92:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for(int j = 0;j < v.size()-1;j++){
      |                       ~~^~~~~~~~~~~~
walk.cpp:103:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int j = 0;j < v.size()-1;j++){
      |                       ~~^~~~~~~~~~~~
walk.cpp: In function 'void usaco_problem()':
walk.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen("milkvisits.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
walk.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("milkvisits.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
walk.cpp: In function 'void init()':
walk.cpp:43:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 | freopen("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
walk.cpp:45:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 | freopen("output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...