結果

問題 No.317 辺の追加
ユーザー koyumeishi
提出日時 2015-12-10 02:10:47
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,168 bytes
コンパイル時間 1,272 ms
コンパイル使用メモリ 105,056 KB
実行使用メモリ 11,780 KB
最終ジャッジ日時 2024-09-15 07:17:58
合計ジャッジ時間 21,195 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 36 TLE * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:68:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   68 |                 scanf("%d%d", &u, &v);
      |                 ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
class UnionFindTree{
    typedef struct {
        int parent;
        int rank;
    }base_node;
    
    vector<base_node> node;
public:
    UnionFindTree(int n){
        node.resize(n);
        for(int i=0; i<n; i++){
            node[i].parent=i;
            node[i].rank=0;
        }
    }
    int find(int x){
        if(node[x].parent == x) return x;
        else{
            return node[x].parent = find(node[x].parent);
        }
    }
    
    bool same(int x, int y){
        return find(x) == find(y);
    }
    void unite(int x, int y){
        x = find(node[x].parent);
        y = find(node[y].parent);
        if(x==y) return;
        if(node[x].rank < node[y].rank){
            node[x].parent = y;
        }else if(node[x].rank > node[y].rank){
            node[y].parent = x;
        }else{
            node[x].rank++;
            unite(x,y);
        }
    }
};
#include <bitset>
typedef bitset<100000> bits;
#include <cassert>
int main(){
    int n,m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    UnionFindTree uft(n);
    for(int i=0; i<m; i++){
        int u,v;
        scanf("%d%d", &u, &v);
        u--;v--;
        g[u].push_back(v);
        g[v].push_back(u);
        uft.unite(u,v);
    }
    vector<int> cnt(n, 0);
    for(int i=0; i<n; i++){
        int r = uft.find(i);
        cnt[r]++;
    }
    map<int,int> w;
    vector<int> unko;
    for(int i=0; i<n; i++){
        if(cnt[i]) w[cnt[i]] += 1;
        if(cnt[i]) unko.push_back(cnt[i]);
    }
    sort(unko.rbegin(), unko.rend());
    vector<int> ans(n+1, 5*n);
    queue<int> pos;
    pos.push(0);
    ans[0] =-1;
    //for(int i=0; i<unko.size(); i++){
    for(auto itr=w.rbegin(); itr!=w.rend(); itr++){
        vector<int> next;
        while(pos.size()){
            int p = pos.front();
            pos.pop();
            next.push_back(p);
            for(int k=0; k<itr->second; k++){
                if(ans[p + itr->first] > ans[p] + 1){
                    ans[p + itr->first] = ans[p] + 1;
                    next.push_back(p + itr->first);
                    p += itr->first;
                }
            }
        }
        sort(next.begin(), next.end());
        next.erase( unique(next.begin(), next.end()), next.end());
        for(auto itr_=next.rbegin(); itr_!=next.rend(); itr_++){
            pos.push(*itr_);
        }
    }
    for(int i=1; i<=n; i++){
        if(ans[i] == 5*n) ans[i] = -1;
        printf("%d\n", ans[i]);
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0