Submission #722021

#TimeUsernameProblemLanguageResultExecution timeMemory
722021ZflopCrocodile's Underground City (IOI11_crocodile)C++14
0 / 100
1 ms212 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; /* ID: 10002181 LANG: C++ TASK: lamps */ using str = string; // yay python! using ld = long double; // or double, if TL is tight using ll = long long; using int64 = ll; using db = double; using ull = unsigned long long; #define ch() getchar() #define pc(x) putchar(x) #define tcT template<class T #define tcTU tcT, class U tcT> using V = vector<T>; tcT, size_t SZ> using AR = array<T,SZ>; using vi = V<int>; using vb = V<bool>; using vpi = V<pair<int,int>>; using vvi = V<vi>; using vl = V<ll>; using vd = V<ld>; using vstr = V<str>; #define all(x) begin(x), end(x) #define sor(x) sort(all(x)) #define rev(x) reverse(all(x)) #define sz(x) (int)(x).size() #define rall(x) x.rbegin(), x.rend() #define AR array // loops #define F0R(i, a, b) for (int i=a; i<b;++i) #define FOR(i, a) for (int i=0; i<a;++i) #define FORn(i, a) for (int i=1; i<=a;++i) #define ROF(i,a) for(int i=a-1; i >= 0;--i) #define R0F(i,a,b) for(int i=a; i > b;--i) #define ROFn(i,a) for(int i=a; i > 0;--i) #define rep(a) F0R(_, a) #define trav(i,x) for(auto& i:x) // pairs #define mp make_pair #define pi pair <int, int> #define f first #define s second // vectors #define lb lower_bound #define ub upper_bound #define SUM(v) accumulate(all(v), 0LL) #define MN(v) *min_element(all(v)) #define MX(v) *max_element(all(v)) #define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end()) #define eb emplace_back #define ft front() #define bk back() #define ins insert #define pf push_front #define pb push_back #define emt empty() #define rsz resize #define pob pop_back() #define pof pop_front() #define swp(a,b) a^=b^=a^=b #define ts to_string #define setIO() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) ll MOD = 1e9+7; const ll MAX = 100000000000; const ll INF = 1e18; // not too close to LLONG_MAX const ld PI = acos((ld)-1); #ifdef _DEBUG freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!! tcT> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } // set a = min(a,b) tcT> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } tcTU> T fstTrue(T lo, T hi, U f) { hi ++; assert(lo <= hi); // assuming f is increasing while (lo < hi) { // find first index such that f is true T mid = lo+(hi-lo)/2; f(mid) ? hi = mid : lo = mid+1; } return lo; } tcTU> T lstTrue(T lo, T hi, U f) { lo --; assert(lo <= hi); // assuming f is decreasing while (lo < hi) { // find first index such that f is true T mid = lo+(hi-lo+1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; } //INPUT #define tcTUU tcT, class ...U tcT> void re(complex<T>& c); tcTU> void re(pair<T,U>& p); tcT> void re(V<T>& v); tcT, size_t SZ> void re(AR<T,SZ>& a); tcT> void re(T& x) { cin >> x; } void re(db& d) { str t; re(t); d = stod(t); } void re(ld& d) { str t; re(t); d = stold(t); } tcTUU> void re(T& t, U&... u) { re(t); re(u...); } tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; } tcTU> void re(pair<T,U>& p) { re(p.f,p.s); } tcT> void re(V<T>& x) { trav(a,x) re(a); } tcT> void rv(int n, V<T>& x) { x.rsz(n); re(x); } //OUTPUT namespace output { tcT> void PS(V<T>& x) { FOR(i,sz(x)) cout << x[i] << " \n"[i + 1 == sz(x)];} tcT> void W(pair<T,T>& x) { cout << x.f << ' ' << x.s << '\n'; } tcT> void PS(bool ok) { if(ok) cout << "YES\n"; else cout << "NO\n"; } template<class T1, class T2> void pr(const pair<T1,T2>& x); tcT, size_t SZ> void pr(const array<T,SZ>& x); tcT> void pr(const vector<T>& x); tcT> void pr(const set<T>& x); template<class T1, class T2> void pr(const map<T1,T2>& x); tcT> void pr(const T& x) { cout << x; } template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) { pr(first); pr(rest...); } template<class T1, class T2> void pr(const pair<T1,T2>& x) { pr("{",x.f,", ",x.s,"}"); } tcT> void prContain(const T& x) { pr("{"); bool fst = 1; trav(a,x) pr(!fst?", ":"",a), fst = 0; pr("}"); } tcT, size_t SZ> void pr(const array<T,SZ>& x) { prContain(x); } tcT> void pr(const vector<T>& x) { prContain(x); } tcT> void pr(const set<T>& x) { prContain(x); } template<class T1, class T2> void pr(const map<T1,T2>& x) { prContain(x); } void ps() { pr("\n"); } // print w/ spaces template<class Arg> void ps(const Arg& first) { pr(first,"\n"); } template<class Arg, class... Args> void ps(const Arg& first, const Args&... rest) { pr(first," "); ps(rest...); } } using namespace output; template<class T,class V> void add(T& a, const V& b) { a = (a + b) % MOD; } template<class T,class V> void sub(T& a, const V& b) { a = (a - b + MOD) % MOD; } template<class T,class V> void mult(T& a, const V& b) { a = a * b % MOD; } void setF(string fileName = "") { ios_base::sync_with_stdio(0); cin.tie(0); if((int)fileName.size()) { freopen((fileName+".in").c_str(), "r", stdin); freopen((fileName+".out").c_str(), "w", stdout); } } vb bb; vi SIEVE(int N){ // sieve in O(N logN) vi pr; bb.rsz(N); bb[0] = bb[1] = true; vi g(N); F0R(i,2,N){ if(!bb[i]){ pr.pb(i); for (int j = i + i; j < N; j += i) bb[j] = true; } } return pr; } template<class T> using ordset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; struct edge{ int a; int b; int w; }; ll POW(ll x, ll y,ll mod = INF){ ll res = 1LL; x %= mod; while(y){ if (y & 1LL) res *= x; res %= mod; x = (x*x) % mod; y >>= 1LL; } return res; } ll gauss(ll n) { return n * (n + 1ll) / 2; } ll fact(ll x) { if(x) return x * fact(x - 1ll); return 1; } vl fc; void F(int N,ll MOD){ fc.rsz(N + 1); fc[0] = 1; FORn(i,N) fc[i] = fc[i - 1] * i * 1ll % MOD; } vl inv; void I(int N,ll MOD){ inv.rsz(N + 1); inv[N] = POW(fc[N],MOD - 2,MOD); for (int i = N; i ;--i) inv[i - 1] = inv[i] * 1ll * i % MOD; } ll Cr(ll N,ll K,ll mod){ if(K < 0) return 0; if(K > N) return 0; return fc[N] * 1ll * inv[K] % mod * inv[N - K] % mod; } ll Ar(ll N,ll K,ll mod){ return fc[N] * inv[N - K] % mod; } ll iv(int k,ll MOD){ return POW(k,MOD-2,MOD); } /* scanf("%lld", &testInteger); printf("%lld", testInteger); ____ ____ ____ ____ ____ ____ ||f |||l |||o |||p |||p ||||y || ||__|||__|||__|||__|||__||||__|| |/__\|/__\|/__\|/__\|/__\||/__\| **/ const int inf = INF; int travel_plan(int N, int M, int in[][2], int tm[], int K, int r[]){ V<vpi> A(N + 1); FOR(i,M){ int a = in[i][0]; int b = in[i][1]; int c = tm[i]; A[a].pb({b,c}); A[b].pb({a,c}); } auto djs = [&] (){ vpi cost(N,{inf,inf}); priority_queue<vi,vvi,greater<vi>>pq; FOR(i,K){ cost[r[i]] = {0,0}; pq.push({0,0,r[i]}); } while(sz(pq)){ auto node = pq.top(); int a = node[0]; int b = node[1]; int c = node[2]; pq.pop(); if(cost[c].f < a || a == INF) continue; if(cost[c].f == a && cost[c].s < b) continue; trav(x,A[c]) if(cost[x.f].s > a + x.s){ cost[x.f].f = cost[x.f].s; cost[x.f].s = a + x.s; pq.push({cost[x.f].f,cost[x.f].s,x.f}); } else if(cost[x.f].f > a + x.s){ cost[x.f].f = a + x.s; pq.push({cost[x.f].f,cost[x.f].s,x.f}); } } return cost[0].f; }; return djs(); }

Compilation message (stderr)

crocodile.cpp:267:17: warning: overflow in conversion from 'll' {aka 'long long int'} to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
  267 | const int inf = INF;
      |                 ^~~
crocodile.cpp: In function 'void setF(std::string)':
crocodile.cpp:184:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |   freopen((fileName+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
crocodile.cpp:185:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |   freopen((fileName+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...