#53486 (C++11) No.277 根掘り葉掘り

• 問題: No.277 根掘り葉掘り
• ユーザー: 唐澤貴洋
• 提出日時: 2015-10-12 23:34:21
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 1,241 bytes
• コンパイル時間: 958 ms
• コンパイル使用メモリ: 84,868 KB
• 実行使用メモリ: 12,564 KB
• 最終ジャッジ日時: 2024-07-21 07:20:59
• 合計ジャッジ時間: 4,744 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,812 KB
testcase_01	AC	2 ms; 6,940 KB
testcase_02	AC	2 ms; 6,944 KB
testcase_03	AC	2 ms; 6,944 KB
testcase_04	AC	2 ms; 6,944 KB
testcase_05	AC	2 ms; 6,940 KB
testcase_06	AC	2 ms; 6,944 KB
testcase_07	WA	-
testcase_08	AC	2 ms; 6,944 KB
testcase_09	WA	-
testcase_10	AC	209 ms; 12,196 KB
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-

ソースコード

#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<list>
#include<stack>
#include<queue>
#include<bitset>
#include<array>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstdlib>
#define D int
#define U unsigned
using namespace std;
D n, m,a, b, d, e, x, y, z;
D i, j, k;
struct Li {
	int n;
	int p;
	int r;
	int l;
	bool leaf;
	bool fl;
	vector<int> near;
	bool operator<(const Li &obj)const {
		return n < obj.n;
	}
};
int main() {
	D t;
	queue<D> que;
	vector<Li> tr;
	Li li = {};
	cin >> a;
	li.n = 0;
	li.p = -1;
	li.r = 0;
	li.leaf = true;
	tr.push_back(li);
	for (i = 1; i < a; i++) {
		cin >> li.p >> li.n;
		li.n--;
		li.p--;
		tr.push_back(li);
	}
	sort(begin(tr),end(tr));
	for (i = 1; i < a; i++) {
		tr[i].r = tr[tr[i].p].r + 1;
		tr[i].near.push_back(tr[i].p);
		tr[tr[i].p].near.push_back(i);
		if (tr[tr[i].p].leaf)
			tr[tr[i].p].leaf = false;
		tr[i].leaf = true;
	}
	for (i = 0; i < a; i++) {
		if (tr[i].leaf)
			que.push(i);
	}
	while (!que.empty()) {
		t = que.front();
		que.pop();
		tr[t].fl = true;
		for (auto z : tr[t].near) {
			if (!tr[z].fl) {
				tr[z].fl = true;
				tr[z].l = tr[t].l + 1;
				que.push(z);
			}
		}
	}
	for (auto z : tr)
		cout << min(z.r, z.l) << endl;
}