結果

問題 No.317 辺の追加
ユーザー vjudge1
提出日時 2025-01-19 11:58:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,178 bytes
コンパイル時間 1,437 ms
コンパイル使用メモリ 159,708 KB
実行使用メモリ 18,328 KB
最終ジャッジ日時 2025-01-19 11:59:20
合計ジャッジ時間 30,342 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other WA * 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";
		else
			cout << dp[i] << endl;
	}
		
    return 0;
}
0