結果
| 問題 | No.1582 Vertexes vs Edges |
| ユーザー |
 PCTprobability
|
| 提出日時 | 2021-07-02 22:05:58 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 9,219 bytes |
| コンパイル時間 | 3,821 ms |
| コンパイル使用メモリ | 259,540 KB |
| 最終ジャッジ日時 | 2025-01-22 16:02:49 |
|
ジャッジサーバーID （参考情報） |
judge2 / 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 ‘std::_Bvector_base<std::allocator<bool> >::_Bvector_impl::~_Bvector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = long unsigned int]’: target specific option mismatch
184 | ~allocator() _GLIBCXX_NOTHROW { }
| ^
In file included from /usr/include/c++/13/vector:67,
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_bvector.h:590:14: note: called from here
590 | struct _Bvector_impl
| ^~~~~~~~~~~~~
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#pragma GCC optimize("Ofast")#include <bits/stdc++.h>#include <unistd.h>using namespace std;#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endifusing ll = long long;using ld = long double;using ull = long long;#define endl "\n"#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)#define ALL(x) begin(x), end(x)#define all(s) (s).begin(),(s).end()//#define rep2(i, m, n) for (int i = (m); i < (n); ++i)//#define rep(i, n) rep2(i, 0, n)#define PB push_back#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)#define drep(i, n) drep2(i, n, 0)#define rever(vec) reverse(vec.begin(), vec.end())#define sor(vec) sort(vec.begin(), vec.end())#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)#define fi first#define se second#define pb push_back#define P pair<ll,ll>//const ll mod = 998244353;const ll mod = 1000000007;const ll inf = 4500000000000000000ll;static const long double pi = 3.141592653589793;template<class T>void vcin(vector<T> &n){for(int i=0;i<int(n.size());i++) cin>>n[i];}template<class T,class K>void vcin(vector<T> &n,vector<K> &m){for(int i=0;i<int(n.size());i++) cin>>n[i]>>m[i];}template<class T>void vcout(vector<T> &n){for(int i=0;i<int(n.size());i++){cout<<n[i]<<" ";}cout<<endl;}template<class T>void vcin(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cin>>n[i][j];}}}template<class T>void vcout(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cout<<n[i][j]<<" ";}cout<<endl;}cout<<endl;}void yes(bool a){cout<<(a?"yes":"no")<<endl;}void YES(bool a){cout<<(a?"YES":"NO")<<endl;}void Yes(bool a){cout<<(a?"Yes":"No")<<endl;}void possible(bool a){ cout<<(a?"possible":"impossible")<<endl; }void Possible(bool a){ cout<<(a?"Possible":"Impossible")<<endl; }void POSSIBLE(bool a){ cout<<(a?"POSSIBLE":"IMPOSSIBLE")<<endl; }template<class T>auto min(const T& a){ return *min_element(all(a)); }template<class T>auto max(const T& a){ return *max_element(all(a)); }template<class T,class F>void print(pair<T,F> a){cout<<a.fi<<" "<<a.se<<endl;}template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0;}template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0;}template<class T> void ifmin(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}template<class T> void ifmax(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}template<typename T,typename ...Args>auto make_vector(T x,int arg,Args ...args){if constexpr(sizeof...(args)==0)return vector<T>(arg,x);else returnvector(arg,make_vector<T>(x,args...));}ll modPow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }vector<ll> divisor(ll x){ vector<ll> ans; for(ll i = 1; i * i <= x; i++){ if(x % i == 0) {ans.push_back(i); if(i*i!=x){ ans.push_back(x / ans[i]);}}}sor(ans); return ans; }template<class T>struct Sum{vector<T> data;Sum(const vector<T>& v):data(v.size()+1){for(ll i=0;i<v.size();i++) data[i+1]=data[i]+v[i];}T get(ll l,ll r) const {return data[r]-data[l];}};template<class T>struct Sum2{vector<vector<T>> data;Sum2(const vector<vector<T>> &v):data(v.size()+1,vector<T>(v[0].size()+1)){for(int i=0;i<v.size();i++) for(int j=0;j<v[i].size();j++) data[i+1][j+1]=data[i][j+1]+v[i][j];for(int i=0;i<v.size();i++) for(int j=0;j<v[i].size();j++) data[i+1][j+1]+=data[i+1][j];}T get(ll x1,ll y1,ll x2,ll y2) const {return data[x2][y2]+data[x1][y1]-data[x1][y2]-data[x2][y1];}};void cincout(){ios::sync_with_stdio(false);std::cin.tie(nullptr);cout<< fixed << setprecision(20);}struct graph{struct edge{ll to,cost;};ll v;vector<vector<edge>> g;vector<ll> d;vector<bool> negative;vector<bool> diameter;vector<ll> topological_sort;ll diametercost;bool bipartitecheck;vector<ll> bipartite;graph(ll n){init(n);}void init(ll n){v=n;g.resize(n);d.resize(n);negative.resize(n);diameter.resize(n);bipartite.resize(n);for(int i=0;i<v;i++){d[i]=inf;bipartite[i]=-1;negative[i]=false;diameter[i]=false;}}void addedge(ll s,ll t,ll cost){edge e;e.to=t;e.cost=cost;g[s].push_back(e);}void dijkstra(ll s){for(int i=0;i<v;i++){d[i]=inf;}d[s]=0;priority_queue<P,vector<P>,greater<P>> que;que.push(P(0,s));while(!que.empty()){P p=que.top();que.pop();ll V=p.second;if(d[V]<p.first) continue;for(auto e:g[V]){if(d[e.to]>d[V]+e.cost){d[e.to]=d[V]+e.cost;que.push(P(d[e.to],e.to));}}}}void BellmanFord(ll s){for(int i=0;i<v;i++){d[i]=inf;negative[i]=false;}d[s]=0;for(int i=0;i<v;i++){for(int V=0;V<v;V++){if(d[V]==inf){continue;}for(auto e:g[V]){if(d[e.to]>d[V]+e.cost){d[e.to]=d[V]+e.cost;if(i==v-1){negative[e.to]=true;negative[V]=true;}}}}}}void dfs(ll s){for(int i=0;i<v;i++){d[i]=inf;}d[s]=0;dfs2(s,-1);}void dfs2(ll s,ll v){for(auto e:g[s]){if(e.to==v) continue;if(d[e.to]>d[s]+e.cost){d[e.to]=d[s]+e.cost;dfs2(e.to,s);}}}void treediameter(){dfs(0);ll p=0;ll q=0;for(int i=0;i<v;i++){if(q<d[i]){q=d[i];p=i;}}diameter[p]=true;dfs(p);ll p2=0;ll q2=0;for(int i=0;i<v;i++){if(q2<d[i]){q2=d[i];p2=i;}}diameter[p2]=true;diametercost=d[p2];}void Bipartite(){for(int i=0;i<v;i++){if(bipartite[i]==-1){Bipartitedfs(i);}}}void Bipartitedfs(ll s,ll cur=0){bipartite[s]=cur;for(auto e:g[s]){if(bipartite[e.to]!=-1){if((bipartite[e.to]==bipartite[s])^(!e.cost%2)){bipartitecheck=false;}}else{if(e.cost%2){Bipartitedfs(e.to,1-cur);}else{Bipartitedfs(e.to,cur);}}}}void topologicalsort(){for(int i=0;i<v;i++){d[i]=0;}for(int i=0;i<v;i++){if(d[i]) continue;topologicaldfs(i);}rever(topological_sort);}void topologicaldfs(ll a){d[a]=1;for(auto e:g[a]){if(d[e.to]) continue;topologicaldfs(e.to);}topological_sort.push_back(a);}};struct HopcroftKarp {vector< vector< int > > graph;vector< int > dist, match;vector< bool > used, vv;HopcroftKarp(int n, int m) : graph(n), match(m, -1), used(n) {}void add_edge(int u, int v) {graph[u].push_back(v);}void bfs() {dist.assign(graph.size(), -1);queue< int > que;for(int i = 0; i < graph.size(); i++) {if(!used[i]) {que.emplace(i);dist[i] = 0;}}while(!que.empty()) {int a = que.front();que.pop();for(auto &b : graph[a]) {int c = match[b];if(c >= 0 && dist[c] == -1) {dist[c] = dist[a] + 1;que.emplace(c);}}}}bool dfs(int a) {vv[a] = true;for(auto &b : graph[a]) {int c = match[b];if(c < 0 || (!vv[c] && dist[c] == dist[a] + 1 && dfs(c))) {match[b] = a;used[a] = true;return (true);}}return (false);}int bipartite_matching() {int ret = 0;while(true) {bfs();vv.assign(graph.size(), false);int flow = 0;for(int i = 0; i < graph.size(); i++) {if(!used[i] && dfs(i)) ++flow;}if(flow == 0) return (ret);ret += flow;}}void output() {for(int i = 0; i < match.size(); i++) {if(~match[i]) {cout << match[i] << "-" << i << endl;}}}};int main() {cincout();ll a;cin>>a;vector<P> b;graph gr(a);for(int i=0;i<a-1;i++){ll x,y;cin>>x>>y;x--;y--;gr.addedge(x,y,1);gr.addedge(y,x,1);b.pb({x,y});}gr.Bipartite();ll c=0;for(int i=0;i<a;i++){c+=gr.bipartite[i];}HopcroftKarp gm(c,a-c);//cout<<c<<" "<<a-c<<endl;ll c1=0,c2=c;map<ll,ll> t;for(int i=0;i<a;i++){if(gr.bipartite[i]){// g.add_edge(a,c1,1,0);// cout<<a<<" "<<c1<<endl;t[i]=c1;c1++;}else{t[i]=c2;// g.add_edge(c2,a+1,1,0);// cout<<c2<<" "<<a+1<<endl;c2++;}}for(int i=0;i<a-1;i++){if(t[b[i].fi]<c){gm.add_edge(t[b[i].fi],t[b[i].se]-c);// cout<<t[b[i].fi]<<" "<<t[b[i].se]-c<<endl;}else{gm.add_edge(t[b[i].se],t[b[i].fi]-c);// cout<<t[b[i].se]<<" "<<t[b[i].fi]-c<<endl;}}cout<<gm.bipartite_matching()<<endl;}