oj.uz

Submission #379722

# Submission time Handle Problem Language Result Execution time Memory
379722 2021-03-19T05:11:21 Z wzy Džumbus (COCI19_dzumbus) C++11
110 / 110
 305 ms 59372 KB 
#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);
	}
}

Compilation message

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);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 45712 KB Output is correct
2 Correct 248 ms 53228 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 45712 KB Output is correct
2 Correct 248 ms 53228 KB Output is correct
3 Correct 287 ms 59372 KB Output is correct
4 Correct 305 ms 45068 KB Output is correct
5 Correct 303 ms 42220 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1516 KB Output is correct
2 Correct 52 ms 2284 KB Output is correct
3 Correct 53 ms 2796 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 45712 KB Output is correct
2 Correct 248 ms 53228 KB Output is correct
3 Correct 287 ms 59372 KB Output is correct
4 Correct 305 ms 45068 KB Output is correct
5 Correct 303 ms 42220 KB Output is correct
6 Correct 51 ms 1516 KB Output is correct
7 Correct 52 ms 2284 KB Output is correct
8 Correct 53 ms 2796 KB Output is correct
9 Correct 89 ms 5228 KB Output is correct
10 Correct 68 ms 4076 KB Output is correct
11 Correct 70 ms 3308 KB Output is correct