結果
| 問題 | No.119 旅行のツアーの問題 |
| ユーザー |
 get_tanni
|
| 提出日時 | 2024-07-25 13:06:35 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 5,062 bytes |
| コンパイル時間 | 4,521 ms |
| コンパイル使用メモリ | 336,408 KB |
| 最終ジャッジ日時 | 2025-02-23 15:49:42 |
| 合計ジャッジ時間 | 4,911 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
In file included from /usr/include/c++/13/string:43,
from /usr/include/c++/13/bitset:52,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
from main.cpp:5:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<long long int, std::allocator<long long int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = long long int]’: target specific option mismatch
184 | ~allocator() _GLIBCXX_NOTHROW { }
| ^
In file included from /usr/include/c++/13/vector:66,
from /usr/include/c++/13/functional:64,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
133 | struct _Vector_impl
| ^~~~~~~~~~~~
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>#include <atcoder/all>using std::cout; using namespace std; using ll=long long; using ld=long double; using P=array<ll,2>; using mint = atcoder::modint998244353;#define rep(i,n) for (ll i=0,siz=(n);i<siz;i++)#define rep2(i,a,b) for (ll i=(a),siz=(b);i<siz;i++)#define repd(i,a,b) for (ll i=(a),siz=(b);i>=siz;i--)#define popcount __builtin_popcountll#define cin(a) ll a; cin >> a;#define cin2(a,b) ll a,b; cin >> a >> b;#define cin3(a,b,c) ll a,b,c; cin >> a >> b >> c;#define cinvec(v) vector<ll> v(N); rep(i,N) cin >> v[i];#define cinvec2(v,n) vector<ll> v(n); rep(i,n) cin >> v[i];#define cins(s) string s; cin >> s;#define cinc(c) char c; cin >> c;vector<ll> dx = {0,-1,0,1},dy = {1,0,-1,0}, ddx = {0,-1,-1,-1,0,1,1,1}, ddy = {1,1,0,-1,-1,-1,0,1};void yesno(bool b) {cout << (b?"Yes":"No") << endl;}template<class T> void sortunique(vector<T> &V) {sort(V.begin(), V.end()); V.erase(unique(V.begin(), V.end()), V.end());}template<typename T> void outvec(const std::initializer_list<T>& list) { bool first = true; for (const auto& elem : list){ if (!first) std::cout << " "; std::cout << elem; first = false; } std::cout << std::endl; }template<typename T> void outvec(const std::vector<T>& vec) { bool first = true; for (const auto& elem : vec){ if (!first) std::cout << " "; std::cout << elem; first = false; } std::cout << std::endl; }template<typename T, size_t N> void outvecp(const std::vector<std::array<T,N>>& vec) { bool first = true; for (const auto& elem : vec){ if (!first) std::cout << " "; for (int i = 0; i < N; i++) std::cout << elem[i] << " "; first = false; } std::cout << std::endl; }vector<ll> compress(vector<ll> &A){vector<ll> B = A; sortunique(B); rep(i,A.size()) A[i] = lower_bound(B.begin(),B.end(),A[i]) - B.begin(); return B;}ll bs(ll l, ll r, function<bool(ll)> f) { while (r-l > 1) { ll m = (l+r)/2; if (f(m)) r = m; else l = m; } return r; }ll msb(ll N) { assert(N>0); return 63 - __builtin_clzll(N); }class Dinic_MaximFlow{private:struct Edge{ll to;ll cap;ll rev;};vector<vector<Edge>> G;vector<ll> level;vector<ll> iter;ll N;void bfs(ll s){for (ll i=0;i<N;i++) level[i] = -1;queue<ll> que;level[s] = 0;que.push(s);while(!que.empty()){ll v = que.front(); que.pop();for (ll i=0;i<G[v].size();i++){Edge &e = G[v][i];if (e.cap > 0 && level[e.to] < 0){level[e.to] = level[v] + 1;que.push(e.to);}}}}ll dfs(ll v, ll t, ll f){if (v == t) return f;for (ll &i=iter[v];i<G[v].size();i++){Edge &e = G[v][i];if (e.cap > 0 && level[v] < level[e.to]){ll d = dfs(e.to, t, min(f, e.cap));if (d > 0){e.cap -= d;G[e.to][e.rev].cap += d;return d;}}}return 0;}public:Dinic_MaximFlow(ll n){N = n;G.resize(n);level.resize(n);iter.resize(n);}void add_edge(ll from, ll to, ll cap){G[from].push_back((Edge){to, cap, (ll)G[to].size()});G[to].push_back((Edge){from, 0, (ll)G[from].size()-1});}ll max_flow(ll s, ll t){ll flow = 0;while (true){bfs(s);if (level[t] < 0) return flow;for (ll i=0;i<N;i++) iter[i] = 0;ll f;while ((f = dfs(s, t, 1e18)) > 0){flow += f;}}}vector<vector<Edge>> edges(){return G;}vector<P> matching_res(ll Ns){vector<P> ans;for (ll i=0;i<Ns;i++){for (ll j=0;j<G[i].size();j++){Edge e = G[i][j];if (e.cap == 0) ans.push_back(P{i,e.to});}}return ans;}};int main() {cin(N);vector<ll> B(N),C(N);rep(i,N) cin >> B[i] >> C[i];cin(M);vector<ll> D(M),E(M);rep(i,M) cin >> D[i] >> E[i];Dinic_MaximFlow dm(2*N+2);ll st = 2*N,goal = 2*N+1;rep(i,N) {dm.add_edge(st,i,B[i]+C[i]);dm.add_edge(i,i+N,1e9);dm.add_edge(i,goal,C[i]);dm.add_edge(st,i+N,B[i]);dm.add_edge(i+N,goal,B[i]+C[i]);}rep(i,M) {dm.add_edge(D[i],E[i]+N,1e9);}ll ans = 2*accumulate(C.begin(),C.end(),0LL) + 2*accumulate(B.begin(),B.end(),0LL) - dm.max_flow(st,goal);cout << ans << endl;return 0;}