結果

問題 No.317 辺の追加
ユーザー vjudge1
提出日時 2025-01-19 12:01:00
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,180 bytes
コンパイル時間 1,496 ms
コンパイル使用メモリ 158,828 KB
実行使用メモリ 20,992 KB
最終ジャッジ日時 2025-01-19 12:01:33
合計ジャッジ時間 31,539 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32 TLE * 6
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:40:21: warning: integer overflow in expression of type ‘int’ results in ‘1411065433’ [-Woverflow]
   40 |         dp[i] = maxN*maxN;
      |                     ^

ソースコード

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

#include<bits/stdc++.h>
using namespace std;
#define maxN 100005
int n,m,u,v,dp[maxN];
vector<int> G[maxN],a;
bool vis[maxN];
int dfs(int p)
{
    //cout << p << endl;
    if(vis[p])
        return 0;
    int ans = 1;
    vis[p] = 1;
    if(!G[p].empty())
        for(int i = 0; i < G[p].size(); i++)
            ans += dfs(G[p][i]);
    return ans;
}
int main()
{
   cin >> n >> m;
   for(int i = 1; i <= m; i++)
   {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
   }
    memset(vis,0,sizeof(vis));
    for(int i = 1; i <= n; i++)
    {
        int x = dfs(i);
        if(x != 0)
            a.push_back(x);
    }
    /*for(int i = 0; i < a.size(); i++)
        cout << a[i] << ' ';
    cout << endl;*/
    for(int i = 1; i <= n; i++)
        dp[i] = maxN*maxN;
    dp[0] = 0;
    for(int i = 0; i < a.size(); i++)
    {
        for(int j = n; j > a[i]; j--)
        {
            
            //if(dp[j] > dp[j-a[i]]+1)
            //cout << "dp[" << i << "][" << j << "]=" << "dp[" << i - 1 << "][" << j - a[i] << "]+1=" <<dp[j-a[i]]<<endl;
            dp[j] = min(dp[j],dp[j-a[i]]+1);
        }
        dp[a[i]] = 0;
        
    }
    for(int i = 1; i <= n; i++)
    {
        if(dp[i] > maxN)
            cout << "-1\n";
        else
            cout << dp[i] << endl;
    }
        
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0