Submission #423851

#	Time	Username	Problem	Language	Result	Execution time	Memory
423851		hhhhaura	도로 폐쇄 (APIO21_roads)	C++14	Compilation error	0 ms	0 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 1e12
#define eps (1e-9)
#define MOD 1000000007
using namespace std;
#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<ll> U, vector<ll> V, vector<ll> W) {
	init_(N);
	rep(i, 0, N - 2) add_edge(U[i] + 1, V[i] + 1, W[i]);
	return solve();
}

Compilation message (stderr)

roads.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
roads.cpp:17:2: error: 'll' does not name a type; did you mean 'all'?
   17 |  ll sum, x, cnt;
      |  ^~
      |  all
roads.cpp:18:17: error: 'll' was not declared in this scope; did you mean 'all'?
   18 |  priority_queue<ll> pq;
      |                 ^~
      |                 all
roads.cpp:18:19: error: template argument 1 is invalid
   18 |  priority_queue<ll> pq;
      |                   ^
roads.cpp:18:19: error: template argument 2 is invalid
roads.cpp:18:19: error: template argument 3 is invalid
roads.cpp:19:8: error: 'll' was not declared in this scope; did you mean 'all'?
   19 |  stack<ll> st;
      |        ^~
      |        all
roads.cpp:19:10: error: template argument 1 is invalid
   19 |  stack<ll> st;
      |          ^
roads.cpp:19:10: error: template argument 2 is invalid
roads.cpp:31:11: error: 'll' has not been declared
   31 |  void set(ll _x) { x = max(0ll, _x); }
      |           ^~
roads.cpp:32:11: error: 'll' has not been declared
   32 |  void add(ll v) { pq.push(v), sum += v; }
      |           ^~
roads.cpp:44:2: error: 'll' does not name a type; did you mean 'all'?
   44 |  ll get_val(bool yes) {
      |  ^~
      |  all
roads.cpp: In member function 'void ac::init_()':
roads.cpp:21:3: error: 'sum' was not declared in this scope
   21 |   sum = 0, x = 0, cnt = 0;
      |   ^~~
roads.cpp:21:12: error: 'x' was not declared in this scope
   21 |   sum = 0, x = 0, cnt = 0;
      |            ^
roads.cpp:21:19: error: 'cnt' was not declared in this scope; did you mean 'int'?
   21 |   sum = 0, x = 0, cnt = 0;
      |                   ^~~
      |                   int
roads.cpp:22:12: error: request for member 'size' in '((ac*)this)->ac::st', which is of non-class type 'int'
   22 |   while(st.size()) st.pop();
      |            ^~~~
roads.cpp:22:23: error: request for member 'pop' in '((ac*)this)->ac::st', which is of non-class type 'int'
   22 |   while(st.size()) st.pop();
      |                       ^~~
roads.cpp:23:12: error: request for member 'size' in '((ac*)this)->ac::pq', which is of non-class type 'int'
   23 |   while(pq.size()) pq.pop();
      |            ^~~~
roads.cpp:23:23: error: request for member 'pop' in '((ac*)this)->ac::pq', which is of non-class type 'int'
   23 |   while(pq.size()) pq.pop();
      |                       ^~~
roads.cpp: In member function 'void ac::maintain()':
roads.cpp:26:12: error: request for member 'size' in '((ac*)this)->ac::pq', which is of non-class type 'int'
   26 |   while(pq.size() > x) {
      |            ^~~~
roads.cpp:26:21: error: 'x' was not declared in this scope
   26 |   while(pq.size() > x) {
      |                     ^
roads.cpp:27:4: error: 'll' was not declared in this scope; did you mean 'all'?
   27 |    ll cur = pq.top(); pq.pop();
      |    ^~
      |    all
roads.cpp:27:26: error: request for member 'pop' in '((ac*)this)->ac::pq', which is of non-class type 'int'
   27 |    ll cur = pq.top(); pq.pop();
      |                          ^~~
roads.cpp:28:4: error: 'sum' was not declared in this scope
   28 |    sum -= cur;
      |    ^~~
roads.cpp:28:11: error: 'cur' was not declared in this scope
   28 |    sum -= cur;
      |           ^~~
roads.cpp: In member function 'void ac::set(int)':
roads.cpp:31:20: error: 'x' was not declared in this scope; did you mean '_x'?
   31 |  void set(ll _x) { x = max(0ll, _x); }
      |                    ^
      |                    _x
roads.cpp:31:35: error: no matching function for call to 'max(long long int, int&)'
   31 |  void set(ll _x) { x = max(0ll, _x); }
      |                                   ^
In file included from /usr/include/c++/10/vector:60,
                 from roads.h:1,
                 from roads.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
roads.cpp:31:35: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   31 |  void set(ll _x) { x = max(0ll, _x); }
      |                                   ^
In file included from /usr/include/c++/10/vector:60,
                 from roads.h:1,
                 from roads.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
roads.cpp:31:35: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   31 |  void set(ll _x) { x = max(0ll, _x); }
      |                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from roads.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
roads.cpp:31:35: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   31 |  void set(ll _x) { x = max(0ll, _x); }
      |                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from roads.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
roads.cpp:31:35: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   31 |  void set(ll _x) { x = max(0ll, _x); }
      |                                   ^
roads.cpp: In member function 'void ac::add(int)':
roads.cpp:32:22: error: request for member 'push' in '((ac*)this)->ac::pq', which is of non-class type 'int'
   32 |  void add(ll v) { pq.push(v), sum += v; }
      |                      ^~~~
roads.cpp:32:31: error: 'sum' was not declared in this scope
   32 |  void add(ll v) { pq.push(v), sum += v; }
      |                               ^~~
roads.cpp: In member function 'void ac::pop()':
roads.cpp:34:10: error: request for member 'size' in '((ac*)this)->ac::pq', which is of non-class type 'int'
   34 |   if(!pq.size()) return;
      |          ^~~~
roads.cpp:35:3: error: 'll' was not declared in this scope; did you mean 'all'?
   35 |   ll cur = pq.top(); pq.pop();
      |   ^~
      |   all
roads.cpp:35:25: error: request for member 'pop' in '((ac*)this)->ac::pq', which is of non-class type 'int'
   35 |   ll cur = pq.top(); pq.pop();
      |                         ^~~
roads.cpp:36:6: error: request for member 'push' in '((ac*)this)->ac::st', which is of non-class type 'int'
   36 |   st.push(cur), cnt ++;
      |      ^~~~
roads.cpp:36:11: error: 'cur' was not declared in this scope
   36 |   st.push(cur), cnt ++;
      |           ^~~
roads.cpp:36:17: error: 'cnt' was not declared in this scope; did you mean 'int'?
   36 |   st.push(cur), cnt ++;
      |                 ^~~
      |                 int
roads.cpp:37:3: error: 'sum' was not declared in this scope
   37 |   sum -= cur;
      |   ^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from roads.cpp:3:
roads.cpp: In member function 'void ac::redo()':
roads.cpp:40:10: error: 'cnt' was not declared in this scope; did you mean 'int'?
   40 |   assert(cnt), cnt --;
      |          ^~~
roads.cpp:41:3: error: 'll' was not declared in this scope; did you mean 'all'?
   41 |   ll cur = st.top(); st.pop();
      |   ^~
      |   all
roads.cpp:41:25: error: request for member 'pop' in '((ac*)this)->ac::st', which is of non-class type 'int'
   41 |   ll cur = st.top(); st.pop();
      |                         ^~~
roads.cpp:42:3: error: 'sum' was not declared in this scope
   42 |   sum += cur, pq.push(cur);
      |   ^~~
roads.cpp:42:10: error: 'cur' was not declared in this scope
   42 |   sum += cur, pq.push(cur);
      |          ^~~
roads.cpp:42:18: error: request for member 'push' in '((ac*)this)->ac::pq', which is of non-class type 'int'
   42 |   sum += cur, pq.push(cur);
      |                  ^~~~
roads.cpp: At global scope:
roads.cpp:50:2: error: 'll' does not name a type; did you mean 'all'?
   50 |  ll n, ii, temp;
      |  ^~
      |  all
roads.cpp:51:9: error: 'll' was not declared in this scope; did you mean 'all'?
   51 |  vector<ll> pri, dp0, dp1, deg, vis, es, cost;
      |         ^~
      |         all
roads.cpp:51:11: error: template argument 1 is invalid
   51 |  vector<ll> pri, dp0, dp1, deg, vis, es, cost;
      |           ^
roads.cpp:51:11: error: template argument 2 is invalid
roads.cpp:52:16: error: 'll' was not declared in this scope; did you mean 'all'?
   52 |  vector<vector<ll>> mp;
      |                ^~
      |                all
roads.cpp:52:16: error: template argument 1 is invalid
roads.cpp:52:16: error: template argument 2 is invalid
roads.cpp:52:18: error: template argument 1 is invalid
   52 |  vector<vector<ll>> mp;
      |                  ^~
roads.cpp:52:18: error: template argument 2 is invalid
roads.cpp:54:7: error: variable or field 'init_' declared void
   54 |  void init_(ll _n) {
      |       ^~~~~
roads.cpp:54:13: error: 'll' was not declared in this scope; did you mean 'all'?
   54 |  void init_(ll _n) {
      |             ^~
      |             all
roads.cpp:68:7: error: variable or field 'add_edge' declared void
   68 |  void add_edge(ll a, ll b, ll c) {
      |       ^~~~~~~~
roads.cpp:68:16: error: 'll' was not declared in this scope; did you mean 'all'?
   68 |  void add_edge(ll a, ll b, ll c) {
      |                ^~
      |                all
roads.cpp:68:22: error: 'll' was not declared in this scope; did you mean 'all'?
   68 |  void add_edge(ll a, ll b, ll c) {
      |                      ^~
      |                      all
roads.cpp:68:28: error: 'll' was not declared in this scope; did you mean 'all'?
   68 |  void add_edge(ll a, ll b, ll c) {
      |                            ^~
      |                            all
roads.cpp:75:7: error: variable or field 'dfs' declared void
   75 |  void dfs(ll x, ll par, ll k) {
      |       ^~~
roads.cpp:75:11: error: 'll' was not declared in this scope; did you mean 'all'?
   75 |  void dfs(ll x, ll par, ll k) {
      |           ^~
      |           all
roads.cpp:75:17: error: 'll' was not declared in this scope; did you mean 'all'?
   75 |  void dfs(ll x, ll par, ll k) {
      |                 ^~
      |                 all
roads.cpp:75:25: error: 'll' was not declared in this scope; did you mean 'all'?
   75 |  void dfs(ll x, ll par, ll k) {
      |                         ^~
      |                         all
roads.cpp:119:9: error: 'll' was not declared in this scope; did you mean 'all'?
  119 |  vector<ll> solve() {
      |         ^~
      |         all
roads.cpp:119:11: error: template argument 1 is invalid
  119 |  vector<ll> solve() {
      |           ^
roads.cpp:119:11: error: template argument 2 is invalid
roads.cpp: In function 'int solver::solve()':
roads.cpp:9:18: error: request for member 'begin' in 'solver::pri', which is of non-class type 'int'
    9 | #define all(x) x.begin(), x.end()
      |                  ^~~~~
roads.cpp:120:8: note: in expansion of macro 'all'
  120 |   sort(all(pri), [](ll a, ll b) {return deg[a] < deg[b];});
      |        ^~~
roads.cpp:9:29: error: request for member 'end' in 'solver::pri', which is of non-class type 'int'
    9 | #define all(x) x.begin(), x.end()
      |                             ^~~
roads.cpp:120:8: note: in expansion of macro 'all'
  120 |   sort(all(pri), [](ll a, ll b) {return deg[a] < deg[b];});
      |        ^~~
roads.cpp:120:21: error: 'll' has not been declared
  120 |   sort(all(pri), [](ll a, ll b) {return deg[a] < deg[b];});
      |                     ^~
roads.cpp:120:27: error: 'll' has not been declared
  120 |   sort(all(pri), [](ll a, ll b) {return deg[a] < deg[b];});
      |                           ^~
roads.cpp: In lambda function:
roads.cpp:120:44: error: invalid types 'int[int]' for array subscript
  120 |   sort(all(pri), [](ll a, ll b) {return deg[a] < deg[b];});
      |                                            ^
roads.cpp:120:53: error: invalid types 'int[int]' for array subscript
  120 |   sort(all(pri), [](ll a, ll b) {return deg[a] < deg[b];});
      |                                                     ^
roads.cpp: In function 'int solver::solve()':
roads.cpp:121:13: error: 'n' was not declared in this scope
  121 |   rep(i, 1, n) temp = i, sort(all(mp[i]),
      |             ^
roads.cpp:7:42: note: in definition of macro 'rep'
    7 | #define rep(i, a, b) for(int i = a; i <= b; i++)
      |                                          ^
roads.cpp:121:16: error: 'temp' was not declared in this scope; did you mean 'mp'?
  121 |   rep(i, 1, n) temp = i, sort(all(mp[i]),
      |                ^~~~
      |                mp
roads.cpp:121:37: error: invalid types 'int[int]' for array subscript
  121 |   rep(i, 1, n) temp = i, sort(all(mp[i]),
      |                                     ^
roads.cpp:9:16: note: in definition of macro 'all'
    9 | #define all(x) x.begin(), x.end()
      |                ^
roads.cpp:121:37: error: invalid types 'int[int]' for array subscript
  121 |   rep(i, 1, n) temp = i, sort(all(mp[i]),
      |                                     ^
roads.cpp:9:27: note: in definition of macro 'all'
    9 | #define all(x) x.begin(), x.end()
      |                           ^
roads.cpp:122:7: error: 'll' has not been declared
  122 |    [](ll a, ll b) {return deg[es[a] ^ temp] > deg[es[b] ^ temp];});
      |       ^~
roads.cpp:122:13: error: 'll' has not been declared
  122 |    [](ll a, ll b) {return deg[es[a] ^ temp] > deg[es[b] ^ temp];});
      |             ^~
roads.cpp: In lambda function:
roads.cpp:122:33: error: invalid types 'int[int]' for array subscript
  122 |    [](ll a, ll b) {return deg[es[a] ^ temp] > deg[es[b] ^ temp];});
      |                                 ^
roads.cpp:122:39: error: 'temp' is not captured
  122 |    [](ll a, ll b) {return deg[es[a] ^ temp] > deg[es[b] ^ temp];});
      |                                       ^~~~
roads.cpp:122:5: note: the lambda has no capture-default
  122 |    [](ll a, ll b) {return deg[es[a] ^ temp] > deg[es[b] ^ temp];});
      |     ^
roads.cpp:121:16: note: '<typeprefixerror>temp' declared here
  121 |   rep(i, 1, n) temp = i, sort(all(mp[i]),
      |                ^~~~
roads.cpp:122:53: error: invalid types 'int[int]' for array subscript
  122 |    [](ll a, ll b) {return deg[es[a] ^ temp] > deg[es[b] ^ temp];});
      |                                                     ^
roads.cpp:122:59: error: 'temp' is not captured
  122 |    [](ll a, ll b) {return deg[es[a] ^ temp] > deg[es[b] ^ temp];});
      |                                                           ^~~~
roads.cpp:122:5: note: the lambda has no capture-default
  122 |    [](ll a, ll b) {return deg[es[a] ^ temp] > deg[es[b] ^ temp];});
      |     ^
roads.cpp:121:16: note: '<typeprefixerror>temp' declared here
  121 |   rep(i, 1, n) temp = i, sort(all(mp[i]),
      |                ^~~~
roads.cpp: In function 'int solver::solve()':
roads.cpp:123:10: error: 'll' was not declared in this scope; did you mean 'all'?
  123 |   vector<ll> aa(n, 0);
      |          ^~
      |          all
roads.cpp:123:12: error: template argument 1 is invalid
  123 |   vector<ll> aa(n, 0);
      |            ^
roads.cpp:123:12: error: template argument 2 is invalid
roads.cpp:123:17: error: 'n' was not declared in this scope
  123 |   vector<ll