Submission #1134846

#TimeUsernameProblemLanguageResultExecution timeMemory
1134846darsh_jain_meToll (BOI17_toll)C++20
0 / 100
2 ms320 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define fr(j, l,n) for(int j = l; j < int(n); j++) #define fn(j,n,l) for(int j=n-1;j>=l;j--) #define gets(s) string s; cin>>s; #define all(v) v.begin(),v.end() #define getv(v,n) vector<ll> v(n); fr(i,0,n) cin >> v[i]; #define seev(a) for(auto x:a){cout<<x<<" ";}cout<<endl; #define vl vector<ll> #define ve vector #define vvl vector<vector<ll>> #define vp vector<pair<ll,ll>> #define vc vector<char> #define vvc vector<vector<char>> #define pb push_back #define mp make_pair #define mse multiset<ll> #define se set<ll> #define ma map<ll,ll> #define getmat(v,n,m) vector<vl>v(n,vl(m));fr(i,0,n) {fr (j,0,m) cin>>v[i][j];} #define seemat(mat) for(auto row:mat){seev(row);} #define YES cout<<"YES\n"; #define NO cout<<"NO\n"; using namespace std; using namespace __gnu_pbds; // Define ordered multiset with long long typedef tree<long long, long long, less<long>, rb_tree_tag, tree_order_statistics_node_update> ordered_multimap; typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; vl sieve; void SieveOfEratosthenes(int n) { // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. vl prime(n+1,true); for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p greater than or // equal to the square of it numbers which are // multiple of p and are less than p^2 are // already been marked. for (int i = p * p; i <= n; i += p) prime[i] = false; } } // Print all prime numbers for (int p = 2; p <= n; p++) if (prime[p]) sieve.push_back(p); } bool sortbysec(const pair<ll, ll>& a, const pair<ll, ll>& b) { return (a.second < b.second); } // gives gcd and the other coefficients ll gcd(ll a, ll b, ll& x, ll& y) { if (b == 0) { x = 1; y = 0; return a; } ll x1, y1; ll d = gcd(b, a % b, x1, y1); x = y1; y = x1 - y1 * (a / b); return d; } // a raised to power b ll pwr(ll a, ll b, ll mod = 0){ ll result = 1; if(mod == 0){ while(b){ if(b & 1) result *= a; a *= a; b = b >> 1; } } else { while(b){ if(b & 1){ result *= a; result = result % mod; } a *= a; a = a % mod; b = b >> 1; } } return result; } ll modularinverse(ll a,ll p)// p is prime { return pwr(a,p-2,p); } // to convert string to binary(63 bits) string tobin(ll a) { string s; for (int i = 0; i < 63; i++) { if(a%2==1) { s+='1'; } else { s+='0'; } a>>=1; } return s; } int log2_floor(unsigned long long i) { return i ? 63 - __builtin_clzll(i) : -1; // -1 as log undefined for 0 } // QUESTION DHANG SE PADHNA void combine(vvl &a, vvl &b, ll &k, vvl &c) { for (int i = 0; i < k; i++) { for (int j = 0; j < k; j++) { for (int jj = 0; jj < k; jj++) { c[i][j]=min(c[i][j],a[i][jj]+b[jj][j]); } } } } void solve(ll tc){ ll n=0,m=0,k=0,a=0,b=0,c=0,x=0,y=0,z=0,o; cin>>k>>n>>m>>o; ve<vp> gr(n); ve<ve<vvl>>dist(n,ve<vvl> (log2_floor(n)+1,vvl(5,vl(5,1e18)))); for (int i = 0; i < m; i++) { cin>>a>>b>>x; // gr[a].pb({b,x}); dist[a/k][0][a%k][b%k]=x; } // cout<<'w'<<endl; for(int j=0;j<dist[0].size()-1;j++) { for (int i = 0; i < n/k; i++) { if((i+(1<<(j)))<n) { // cout<<i<<' '<<(1<<j)<<endl; combine(dist[i][j],dist[(i+(1<<(j)))][j],k,dist[i][j+1]); } } } // for (int i = 0; i < n; i++) // { // cout<<i<<' '<<endl; // // vvl ans(k,vl(k,1e18)); // // combine(dist[i][0],dist[i+1][0],k,ans); // // seemat(ans); // // cout<<endl; // seemat(dist[i][1]); // } for (int i = 0; i < o; i++) { cin>>x>>y; vvl ans(k,vl(k, 1e18)); vvl ans2(k,vl(k, 1e18)); for (int i = 0; i < k; i++) { ans2[i][i]=0; } c=x/k,z=y/k; ll inix=x,iniy=y; for (int j = 0; j < dist[0].size(); j++) { // cout<<z<<' '<<c<<endl; if(((z-c) & (1<<j))) { combine(ans2,dist[c][j],k,ans); // x+=1<<j; c+=(1<<j); swap(ans2,ans); for (int jj = 0; jj < k; jj++) { for (int ii = 0; ii < k; ii++) { ans[jj][ii]=1e18; } } } } // seemat(ans2); if(inix/k==iniy/k) { cout<<-1<<endl; } else { if(ans2[inix%k][iniy%k]==1e18) { cout<<-1<<endl; } else { cout<<ans2[inix%k][iniy%k]<<endl; } } } } int main(){ #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t=1; // cin>>t; ll tc=0; while(t--){ tc++; solve(tc); } return 0; }

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:230:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  230 |   freopen("input.txt","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:231:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  231 |   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...