Submission #1107135

#TimeUsernameProblemLanguageResultExecution timeMemory
1107135hihihihawToll (BOI17_toll)C++17
0 / 100
90 ms176712 KiB
#pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define pii pair<int,int> #define sz(v) (int)v.size() #define fi first #define se second #define INF 1223372036854775807 #define MOD 998244353 #define cint(x) int x;cin>>x; #define cinarr(a,n) int a[n];for (int i=0;i<n;i++) cin>>a[i]; #define coutarr(a) for (auto d:a)cout<<d<<" "; cout<<endl; #define coutarrD(a) for (auto d:a) cout<<d.fi<<","<<d.se<<" "; cout<<endl; #define BERKAY_TUP ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define endl '\n' #define ld long double #define mid (start+end)/2 #define vvi vector<vector<int>> int t=1; int interactive=0; int usaco=0; int testCase=0; int bj[50023][5][5][18]; void solve(){ int k,n,m,q; cin>>k>>n>>m>>q; for (int i=0;i<50023;i++){ for (int j=0;j<18;j++){ for (int k1=0;k1<5;k1++){ for (int k2=0;k2<5;k2++){ bj[i][k1][k2][j]=99999999999; } } } } while (m--){ int x,y,c; cin>>x>>y>>c; int g1=x/k,g2=g1+1; bj[g1][x%k][y%k][0]=c; } for (int j=1;j<18;j++){ for (int i=0;i<n/k;i++){ if (i+(1<<j)>n/k) continue; for (int k1=0;k1<k;k1++){ for (int k2=0;k2<k;k2++){ for (int z=0;z<k;z++){ bj[i][k1][k2][j]=min(bj[i][k1][k2][j],bj[i][k1][z][j-1]+bj[i+(1<<(j-1))][z][k2][j-1]); } } } } } while (q--){ int a,b; cin>>a>>b; if (a/k>=b/k){ cout<<"-1"<<endl; return; } int z=b/k-a/k; int ansPrev[k][k]; for (int k1=0;k1<k;k1++){ for (int k2=0;k2<k;k2++){ if (k1!=k2) ansPrev[k1][k2]=99999999999; else ansPrev[k1][k2]=0; } } int ans[k][k]; int pos=a/k; for (int j=0;j<18;j++){ if (z&(1<<j)){ for (int k1=0;k1<k;k1++){ for (int k2=0;k2<k;k2++){ ans[k1][k2]=99999999999; for (int z=0;z<k;z++){ ans[k1][k2]=min(ans[k1][k2],ansPrev[k1][z]+bj[pos][z][k2][j]); //if (k1==0 && k2==2)cout<<" "<<z<<" "<<ansPrev[k1][z]+bj[pos][z][k2][j]<<endl; } //if (k1==0 && k2==2) cout<<ans[k1][k2]<<endl; } } pos+=(1<<j); } } for (int k1=0;k1<k;k1++){ for (int k2=0;k2<k;k2++){ ansPrev[k1][k2]=ans[k1][k2]; } } if (ans[a%k][b%k]>=99999999999) cout<<-1<<endl; else cout<<ans[a%k][b%k]<<endl; } } int32_t main(){ BERKAY_TUP; if (usaco){ freopen("optmilk.in", "r", stdin); freopen("optmilk.out", "w", stdout); } if (!interactive){ #ifdef Local freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); //freopen("wormsort.out", "w", stdout); #endif } if (t==1) solve(); else{ cin>>t; while (t--){testCase++;solve();} } return 0; }

Compilation message (stderr)

toll.cpp: In function 'void solve()':
toll.cpp:42:20: warning: unused variable 'g2' [-Wunused-variable]
   42 |         int g1=x/k,g2=g1+1;
      |                    ^~
toll.cpp: In function 'int32_t main()':
toll.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen("optmilk.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen("optmilk.out", "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...