結果

問題 No.317 辺の追加
ユーザー vjudge1
提出日時 2025-01-19 15:17:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,284 bytes
コンパイル時間 562 ms
コンパイル使用メモリ 62,328 KB
実行使用メモリ 20,620 KB
最終ジャッジ日時 2025-01-19 15:19:17
合計ジャッジ時間 125,794 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 2
other TLE * 38
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int dfs(int&, int)’:
main.cpp:23:1: warning: no return statement in function returning non-void [-Wreturn-type]
   23 | }
      | ^

ソースコード

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

#include<iostream>
using namespace std;
int n,m;
struct pos{
    int to,net;
}r[400005];
int top=1,head[100005],vis[100005],t[100005],w[100005],f[100005],vv[100005],nn[100005];
void add(int a,int b){
    r[top]=(pos){
        b,head[a]
    };
    head[a]=top;
    top++;
}
int dfs(int &cnt,int x){
    cnt++;
    for (int i=head[x];i!=0;i=r[i].net){
        if(vis[r[i].to]==0){
            vis[r[i].to]=1;
            dfs(cnt,r[i].to);
        }
    }
}
int main(){ 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);    
    cin >> n >> m;
    for (int i=1;i<=m;i++){
        int a,b;
        cin >> a >> b;
        add(a,b);
        add(b,a);
    }
    int ttop=1;
    for (int i=1;i<=n;i++){
        int cnt=0;
        if(vis[i]==0){
            vis[i]=1;
            dfs(cnt,i);
            if(vv[cnt]==0)t[ttop++]=cnt;
            vv[cnt]++;      
//          cout << vv[cnt] << " "; 
        }
    }
//  cout  << endl;
    int tt=0;
    for (int i=1;i<=ttop;i++){
        int num=vv[t[i]],v=t[i],e=1;
        while(num>=e){
            w[++tt]=e*v;
            nn[tt]=e;
            num-=e;
            e*=2;
        }
        if(num!=0){
            w[++tt]=num*v;
            nn[tt]=num;         
        }
    }
    f[0]=1;
    for (int i=1;i<=tt;i++){
//      cout << w[i] << "-" << nn[i] << " ";
        for (int j=n;j>=w[i];j--){
            if(f[j]==0)f[j]=1e9;
            if(f[j-w[i]]!=0)f[j]=min(f[j],f[j-w[i]]+nn[i]);
        }
    }
//  cout << endl;
    for (int i=1;i<=n;i++){
        if(f[i]==1e9||f[i]==0)cout << -1 << "\n";
        else cout << f[i]-2 << "\n";
    }
}
/*
6 3
2 3
4 5
5 6
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0