結果
問題 | No.1582 Vertexes vs Edges |
ユーザー |
![]() |
提出日時 | 2021-07-02 22:34:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 68 ms / 2,000 ms |
コード長 | 857 bytes |
コンパイル時間 | 579 ms |
コンパイル使用メモリ | 70,812 KB |
実行使用メモリ | 9,216 KB |
最終ジャッジ日時 | 2024-06-29 12:25:50 |
合計ジャッジ時間 | 2,739 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
//サンプル3のお絵描きを間違えて嵌った… //最大マッチングがそれっぽいですね(証明詰められず)。 //市松模様は多分WAじゃないかなと思うけど、反例すぐ出てこない。 #include <iostream> #include <vector> using namespace std; int n; vector<int> et[100000]; bool used[100000]; int match = 0; void dfs(int p, int v) { if (et[v].size() == 1 && p != -1) { //葉 return; } for (int i = 0; i < et[v].size(); i++) { int nv = et[v][i]; if (nv == p) continue; dfs(v, nv); if (used[v] == false && used[nv] == false) { used[nv] = true; used[v] = true; match++; } } } signed main() { int i; cin >> n; for (i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--; v--; et[u].push_back(v); et[v].push_back(u); } dfs(-1, 0); cout << match << endl; return 0; }