Submission #586468

#TimeUsernameProblemLanguageResultExecution timeMemory
586468hibikiJourney (NOI18_journey)C++11
20 / 100
2 ms4564 KiB
#include<bits/stdc++.h> using namespace std; #define MX 500000001 #define pb push_back #define f first #define s second int n,m,h; vector<pair<int,int> > v[10005]; int dp[10005][105]; int ind[10005]; int main() { scanf("%d %d %d",&n,&m,&h); for(int i = 0; i < n - 1; i++) { for(int j = 0; j < h; j++) { int a,b; scanf("%d %d",&a,&b); if(i >= a) continue; v[i].pb({a,b}); ind[a]++; } } memset(dp, 0, sizeof(dp)); queue<int> q; for(int i = 0; i < n - 1; i++) { if(ind[i] == 0) { q.push(i); dp[i][0] = 1; } } while(!q.empty()) { int nw = q.front(); q.pop(); if(nw != 0) for(int i = 1; i < m; i++) { dp[nw][i] += dp[nw][i - 1]; dp[nw][i] = min(dp[nw][i], MX); } for(auto go: v[nw]) { ind[go.f]--; if(ind[go.f] == 0) q.push(go.f); for(int i = 0; i + go.s < m; i++) { dp[go.f][i + go.s] += dp[nw][i]; dp[go.f][i + go.s] = min(dp[go.f][i + go.s], MX); } } } for(int i = 0; i < m; i++) printf("%d ",dp[n - 1][i]); return 0; }

Compilation message (stderr)

journey.cpp: In function 'int main()':
journey.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d %d %d",&n,&m,&h);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
journey.cpp:22:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |             scanf("%d %d",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...