제출 #423858

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
423858		hhhhaura	도로 폐쇄 (APIO21_roads)	C++14	100 / 100	385 ms	106612 KiB

roads

#define wiwihorz
#include "roads.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define INF 1e15
#define eps (1e-9)
#define MOD 1000000007
using namespace std;
#define ll long long int
#define pii pair<int, int>
#define radom mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
struct ac {
	ll sum, x, cnt;
	priority_queue<ll> pq;
	stack<ll> st;
	void init_() {
		sum = 0, x = 0, cnt = 0;
		while(st.size()) st.pop();
		while(pq.size()) pq.pop();
	}
	void maintain() {
		while(pq.size() > x) {
			ll cur = pq.top(); pq.pop();
			sum -= cur;
		}
	}
	void set(ll _x) { x = max(0ll, _x); }
	void add(ll v) { pq.push(v), sum += v; }
	void pop() {
		if(!pq.size()) return;
		ll cur = pq.top(); pq.pop();
		st.push(cur), cnt ++;
		sum -= cur;
	}
	void redo() {
		assert(cnt), cnt --;
		ll cur = st.top(); st.pop();
		sum += cur, pq.push(cur);
	}
	ll get_val(bool yes) {
		maintain();
		return sum - yes * (pq.size() ? pq.top() : 0);
	}
};
namespace solver {
	ll n, ii, temp;
	vector<ll> pri, dp0, dp1, deg, vis, es, cost;
	vector<vector<ll>> mp;
	vector<ac> s;
	void init_(ll _n) {
		n = _n, ii = 0;
		pri.assign(n, 0);
		dp0.assign(n + 1, 0);
		dp1.assign(n + 1, 0);
		deg.assign(n + 1, 0);
		vis.assign(n + 1, 0);
		s.assign(n + 1, ac());
		mp.assign(n + 1, vector<ll>());
		rep(i, 1, n) {
			pri[i - 1] = i;
			s[i].init_();
		}
	}
	void add_edge(ll a, ll b, ll c) {
		mp[a].push_back(es.size());
		mp[b].push_back(es.size());
		es.push_back(a ^ b);
		cost.push_back(c);
		deg[a] ++, deg[b] ++;
	}
	void dfs(ll x, ll par, ll k) {
		vis[x] = k + 1; 
		dp1[x] = INF, dp0[x] = INF;
		vector<ll> v; 
		ll cnt = 0, sum = 0;
		for(auto i : mp[x]) if(i != par) {
			ll to = es[i] ^ x;
			if(deg[to] <= k) break;
			dfs(to, i, k);
			v.push_back(dp1[to] + cost[i] - dp0[to]);
			sum += dp0[to], cnt ++;
		}
		sort(all(v));
		s[x].set(deg[x] - k);
		s[x].maintain();
		ll to = s[x].x - s[x].pq.size();
		if(v.size() >= to) {
			ll cur = 0;
			rep(i, 0, to - 1) cur += v[i];
			dp0[x] = min(dp0[x], sum + cur + s[x].get_val(0));
			rep(j, to, cnt - 1) {
				cur += v[j];
				s[x].pop(), s[x].set(s[x].x - 1);
				dp0[x] = min(dp0[x], sum + cur + s[x].get_val(0));
			}
			s[x].set(deg[x] - k);
			while(s[x].cnt) s[x].redo();
		}
		s[x].set(deg[x] - k - 1);
		s[x].maintain();
		to = s[x].x - s[x].pq.size();
		if(v.size() >= to) {
			ll cur = 0;
			rep(i, 0, to - 1) cur += v[i];
			dp1[x] = min(dp1[x], sum + cur + s[x].get_val(0));
			rep(j, to, cnt - 1) {
				cur += v[j];
				s[x].pop(), s[x].set(s[x].x - 1);
				dp1[x] = min(dp1[x], sum + cur + s[x].get_val(0));
			}
			s[x].set(deg[x] - k - 1);
			while(s[x].cnt) s[x].redo();
		}
	}
	vector<ll> solve() {
		sort(all(pri), [](ll a, ll b) {return deg[a] < deg[b];});
		rep(i, 1, n) temp = i, sort(all(mp[i]), 
			[](ll a, ll b) {return deg[es[a] ^ temp] > deg[es[b] ^ temp];});
		vector<ll> aa(n, 0);
		rep(i, 0, n - 1) {
			while(ii < n && deg[pri[ii]] <= i) {
			    dp0[pri[ii]] = 0;
			    dp1[pri[ii]] = 0;
				for(auto j : mp[pri[ii]]) {
					ll to = es[j] ^ pri[ii];
					if(deg[to] > i) s[to].add(cost[j]);
				}
				ii++;
			} 
			ll ans = 0;
			rep(j, ii, n - 1) if(vis[pri[j]] != i + 1){
				dfs(pri[j], -1, i);
				ans += dp0[pri[j]];
			}
			aa[i] = ans;
		}
		return aa;
	}
};
using namespace solver;
vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
	init_(N);
	rep(i, 0, N - 2) add_edge(U[i] + 1, V[i] + 1, W[i]);
	return solve();
}

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

roads.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
roads.cpp: In member function 'void ac::maintain()':
roads.cpp:27:19: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   27 |   while(pq.size() > x) {
      |         ~~~~~~~~~~^~~
roads.cpp: In function 'void solver::dfs(long long int, long long int, long long int)':
roads.cpp:92:15: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   92 |   if(v.size() >= to) {
      |      ~~~~~~~~~^~~~~
roads.cpp:107:15: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  107 |   if(v.size() >= to) {
      |      ~~~~~~~~~^~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 17 / 17
• Subtask 6: 25 / 25
• Subtask 7: 22 / 22