結果
問題 |
No.3087 University Coloring
|
ユーザー |
|
提出日時 | 2025-04-04 22:48:25 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 87 ms / 2,000 ms |
コード長 | 6,529 bytes |
コンパイル時間 | 3,301 ms |
コンパイル使用メモリ | 288,948 KB |
実行使用メモリ | 7,328 KB |
最終ジャッジ日時 | 2025-04-04 22:48:35 |
合計ジャッジ時間 | 7,111 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#ifdef poe #define debug(x) cerr<<#x<<": "<<x<<endl #else #define debug(x) // #pragma GCC target("arch=skylake-avx512") // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #endif #include<bits/stdc++.h> using namespace std; using ll=long long; using ull=unsigned long long; using ld=long double; using pi=pair<int,int>; using pll=pair<ll,ll>; using str=string; template<class T>using vec=vector<T>; using vi=vec<int>;using vvi=vec<vi>;using vvvi=vec<vvi>;using vvvvi=vec<vvvi>;using vvvvvi=vec<vvvvi>; using vll=vec<ll>;using vvll=vec<vll>;using vvvll=vec<vvll>;using vvvvll=vec<vvvll>;using vvvvvll=vec<vvvvll>; using vpi=vec<pi>;using vvpi=vec<vpi>;using vvvpi=vec<vvpi>;using vvvvpi=vec<vvvpi>;using vvvvvpi=vec<vvvvpi>; using vpll=vec<pll>;using vvpll=vec<vpll>;using vvvpll=vec<vvpll>;using vvvvpll=vec<vvvpll>;using vvvvvpll=vec<vvvvpll>; template<class T>using pq=priority_queue<T,vector<T>>; template<class T>using pqg=priority_queue<T,vector<T>,greater<T>>; #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define per(i,n) for(int i=(int)(n)-1;0<=i;i--) #define per1(i,n) for(int i=(int)(n);0<i;i--) #define range(i,x) for(auto&i:x) #define range2(i,j,x) for(auto&[i,j]:x) #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define Sort(x) sort((x).begin(),(x).end()) #define troS(x) sort((x).rbegin(),(x).rend()) #define Reverse(x) reverse((x).begin(),(x).end()) #define uniq(x) sort((x).begin(),(x).end());(x).erase(unique((x).begin(),(x).end()),(x).end()) #define nextp(x) next_permutation((x).begin(),(x).end()) #define nextc(x,k) next_combination((x).begin(),(x).end(),k) #define bit(x,i) (((x)>>(i))&1) #define pf push_front #define pb push_back #define df pop_front #define db pop_back #define fi first #define se second #define elif else if #define Yes cout<<"Yes"<<'\n' #define No cout<<"No"<<'\n' #define YN(x) cout<<((x)?"Yes":"No")<<'\n' #define O(x) cout<<(x)<<'\n' template<class S,class T>bool chmin(S&a,T b){if(a>b){a=b;return true;}return false;} template<class S,class T>bool chmax(S&a,T b){if(a<b){a=b;return true;}return false;} template<class S,class T,class U>bool ismid(S a,S b,S c){return a<=b&&b<c;} template<class T>bool next_combination(T l,T r,int k){T m=l+k;if(l==r||l==m||r==m)return false;T t=m;while(l!=t){t--;if(*t<*(r-1)){T d=m;while(*t>=*d)d++;iter_swap(t,d);rotate(t+1,d+1,r);rotate(m,m+(r-d)-1,r);return true;}}rotate(l,m,r);return false;} template<class T>T Min(T a,T b){return a<b?a:b;} template<class T,class...Args>T Min(T a,T b,Args...args){return Min(Min(a,b),args...);} template<class T>T Max(T a,T b){return a>b?a:b;} template<class T,class...Args>T Max(T a,T b,Args...args){return Max(Max(a,b),args...);} template<class T>T Sum(T a){return a;} template<class T,class... Args>T Sum(T a,Args... args){return a+Sum(args...);} template<class T>T Max(const vector<T>&v){return *max_element(all(v));} template<class T>T Min(const vector<T>&v){return *min_element(all(v));} template<class T>T Sum(const vector<T>&v){return accumulate(all(v),T(0));} template<class S,class T>T Max(const pair<S,T>&p){return max(p.first,p.second);} template<class S,class T>T Min(const pair<S,T>&p){return min(p.first,p.second);} template<class S,class T>T Sum(const pair<S,T>&p){return p.first+p.second;} template<class S,class T>istream&operator>>(istream&s,pair<S,T>&p){s>>p.first>>p.second;return s;} template<class S,class T>ostream&operator<<(ostream&s,pair<S,T>&p){s<<p.first<<' '<<p.second<<'\n';return s;} template<class T>istream&operator>>(istream&s,vector<T>&v){for(auto&i:v)s>>i;return s;} template<class T>ostream&operator<<(ostream&s,vector<T>&v){for(auto&i:v)s<<i<<' ';s<<'\n';return s;} template<class F>long long bsearch(long long ok,long long ng,F&f){while(abs(ok-ng)>1){long long mid=(ok+ng)/2;if(f(mid))ok=mid;else ng=mid;}return ok;} const int dxy[5]={0,1,0,-1,0}; const int dx[8]={0,1,0,-1,1,1,-1,-1}; const int dy[8]={1,0,-1,0,1,-1,1,-1}; #define nl '\n' #define sp ' ' #define inf ((1<<30)-(1<<15)) #define INF (1LL<<61) #define mod 998244353 void IO() { ios::sync_with_stdio(false); cin.tie(nullptr); cout<<fixed<<setprecision(30); } void solve(); using namespace std; struct UnionFind { int _n; vector<int> data; // _n 個の要素からなるUnionFind を構築 O(n) UnionFind(int n) : _n(n), data(n, -1) {} // 2 つの要素を併合 O(α(n)) bool merge(int p, int q) { p = root(p); q = root(q); if (p == q) return false; if (q < p) swap(p, q); data[p] += data[q]; data[q] = p; return true; } // 親要素を取得 O(α(n)) int root(int p) { assert(0 <= p && p < _n); if (data[p] < 0) { return p; } else { data[p] = root(data[p]); return data[p]; } } // 親要素を取得 O(α(n)) int operator[](int p) { return root(p); } // 2 つの要素が同じ集合に含まれるか判定 O(α(n)) bool same(int p, int q) { return root(p) == root(q); } // 要素が属する集合の大きさを返す O(α(n)) int size(int p) { return -data[root(p)]; } // UnionFind の連結成分のvector を返す O(n α(n)) vector<vector<int>> groups() { vector<vector<int>> re(_n); for (int i=0; i<_n; i++) re[root(i)].push_back(i); re.erase(remove_if(re.begin(), re.end(), [](vector<int>& v){ return v.empty(); }), re.end()); return re; } }; int main() { IO(); int T=1; // cin >> T; while (T--) solve(); } ll dfs(int x, vvpll &g, vll& dp) { if (dp[x] != -1) return dp[x]; ll ans = 0; for (auto [y, w] : g[x]) { ans = max(ans, dfs(y, g, dp) + w); } return dp[x] = ans; } struct Edge { int u, v, w; bool operator<(const Edge& other) const { return w < other.w; } }; void solve() { int n, m; cin >> n >> m; vector<Edge> edges(m); for (int i = 0; i < m; i++) { cin >> edges[i].u >> edges[i].v >> edges[i].w; edges[i].u--; edges[i].v--; } sort(edges.begin(), edges.end()); reverse(edges.begin(), edges.end()); UnionFind uf(n); ll ans=0; for (int i = 0; i < m; i++) { int u = edges[i].u; int v = edges[i].v; if (uf.root(u) != uf.root(v)) { uf.merge(u, v); ans += edges[i].w; } } cout << ans * 2 << nl; }