Submission #1101870

#TimeUsernameProblemLanguageResultExecution timeMemory
1101870simona1230Toll (BOI17_toll)C++17
17 / 100
136 ms19728 KiB
// Online C++ compiler to run C++ program online #include <bits/stdc++.h> using namespace std; int k,n,m,o; vector<pair<int,int> > v[200001],op[200001]; void read() { cin>>k>>n>>m>>o; for(int i=1;i<=m;i++) { int a,b,t; cin>>a>>b>>t; v[a].push_back({b,t}); op[b].push_back({a,t}); } } pair<int,int> q[200001]; long long p[200001]; void subt1() { for(int i=0;i<n;i++) { p[i+1]=1e9; for(int j=0;j<v[i].size();j++) { long long nb=v[i][j].second; p[i+1]=min(p[i+1],nb); } p[i+1]+=p[i]; } for(int i=1;i<=o;i++) if(p[q[i].second]-p[q[i].first]<1e9)cout<<p[q[i].second]-p[q[i].first]<<endl; else cout<<-1<<endl; exit(0); } long long dp[200001]; void subt2() { int lm=n; for(int i=1;i<n;i++) { dp[i]=1e9; for(int j=0;j<op[i].size();j++) { pair<int,long long> nb=op[i][j]; dp[i]=min(dp[i],dp[nb.first]+nb.second); } } for(int i=1;i<=o;i++) if(dp[q[i].second]<1e9)cout<<dp[q[i].second]<<endl; else cout<<-1<<endl; exit(0); } int lf=0; void solve() { for(int i=1;i<=o;i++) { cin>>q[i].first>>q[i].second; lf=min(lf,q[i].first); } if(k==1)subt1(); if(lf==0)subt2(); } int main() { read(); solve(); return 0; }

Compilation message (stderr)

toll.cpp: In function 'void subt1()':
toll.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
toll.cpp: In function 'void subt2()':
toll.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int j=0;j<op[i].size();j++)
      |                     ~^~~~~~~~~~~~~
toll.cpp:46:9: warning: unused variable 'lm' [-Wunused-variable]
   46 |     int lm=n;
      |         ^~
#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...