제출 #379722

#제출 시각아이디문제언어결과실행 시간메모리
379722wzyDžumbus (COCI19_dzumbus)C++11
110 / 110
305 ms59372 KiB
#include <bits/stdc++.h> using namespace std; #define F first #define S second #define rep(i, a, b) for(int i = a; i < (b); ++i) #define per(i, a, b) for(int i = b-1; i>=a ; i--) #define trav(a, x) for(auto& a : x) #define allin(a , x) for(auto a : x) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<ll> vl; typedef vector<pii> vpi; typedef pair<ll,ll> pll; typedef vector<string> vs; typedef vector<pll> vpl; typedef vector<int> vi; std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count()); const int N = 1005; const ll inf = (ll) 1e15; int n , m , d[N] , vis[N] , sz[N]; vector<int> g[N]; vector< vl > dp[N]; ll cost[N]; void comb(vector<vl> &a , vector<vl> &b){ vector<vl> c(sz(a) + sz(b) + 2, vl(3,inf)); auto add = [&](int a , int b){ if(a == 1){ if(b == 1) return 2; else return (b > 0 ? 1 : 0); } if(a == 2){ return (b == 1 ? 1 : 0); } return 0; }; auto state = [&](int a , int b){ if(a == 1){ if(b > 0) return 2; } if(a == 2){ if(b > 0) return 2; } return a; }; for(int i = 0 ; i < sz(a) ; i ++){ for(int j = 0 ; j < sz(b); j ++){ for(int k = 0 ; k < 3; k ++){ for(int w = 0 ; w < 3 ; w++){ c[i+j+add(k,w)][state(k,w)] = min(c[i+j+add(k,w)][state(k,w)],a[i][k] + b[j][w]); } } } } swap(c,a); } void dfs(int x){ sz[x] = 1; dp[x] = vector<vl>(1,vl(3,0)); dp[x][0][1] = d[x]; dp[x][0][2] = inf; for(auto w : g[x]){ if(!vis[w]){ vis[w] = vis[x]; dfs(w); comb(dp[x] , dp[w]); sz[x] += sz[w]; } } } int32_t main(){ scanf("%d%d" , &n , &m); for(int i = 1 ; i <= n; i ++) scanf("%d" , &d[i]); for(int i = 1; i <= m; i ++){ int u , v; scanf("%d%d" , &u , &v); g[u].push_back(v); g[v].push_back(u); } fill(cost,cost+N,inf); cost[0] = 0; for(int i = 1 ; i <= n; i ++){ if(!vis[i]){ vis[i] = i; dfs(i); for(int j = n; j >= 1; j --){ for(int k = 0 ; k < min(sz(dp[i]),j+1) ; k ++){ cost[j] = min(cost[j] , cost[j-k] + min({dp[i][k][0] , dp[i][k][1] , dp[i][k][2]})); } } for(int j = 1; j <= n; j ++) cost[j] = min(cost[j] , cost[j+1]); } } vl p; for(int i = 0 ; i <= n; i ++){ if(cost[i] >= inf) break; p.push_back(cost[i]); assert(cost[i] <= cost[i+1]); } int q; scanf("%d" , &q); for(int _ = 0 ; _ < q; _ ++){ ll s; scanf("%lld" , & s); int ans = (int) (upper_bound(p.begin() , p.end() , s) - p.begin()) - 1; printf("%d\n" , (int)ans); } }

컴파일 시 표준 에러 (stderr) 메시지

dzumbus.cpp: In function 'int32_t main()':
dzumbus.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |  scanf("%d%d" , &n , &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
dzumbus.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |   scanf("%d" , &d[i]);
      |   ~~~~~^~~~~~~~~~~~~~
dzumbus.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |   scanf("%d%d" , &u , &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
dzumbus.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  112 |  scanf("%d" , &q);
      |  ~~~~~^~~~~~~~~~~
dzumbus.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |   scanf("%lld" , & s);
      |   ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...