提交记录 12929


用户 题目 状态 得分 用时 内存 语言 代码长度
lrw04 noip18d. 【NOIP2018】旅行 Accepted 100 638.044 ms 728 KB C++11 1.65 KB
提交时间 评测时间
2020-07-04 23:13:09 2020-08-01 03:01:39
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
using namespace std;

#define MAXN 5020
#define MAXM (4 * MAXN)
#define INF 0x3f3f3f3f
int n, m, delu, delv;
int hd[MAXN], dst[MAXM], nxt[MAXM], ec = 1;
vector<int> g[MAXN], ans, cur;
bool vis[MAXN];
pair<int, int> edges[MAXM];

void link(int u, int v) {
	nxt[++ec] = hd[u];
	hd[u] = ec;
	dst[ec] = v;
	g[u].push_back(v);
}

void dfs(int s, int fa) {
	ans.push_back(s);
	for (int i = 0; i < (int) g[s].size(); i++)
	if (g[s][i] != fa)
		dfs(g[s][i], s);
}

void tree() {
	dfs(1, 0);
	for (int i = 0; i < n; i++)
		cout << ans[i] << " ";
	cout << endl;
}

inline bool notdel(int u, int v) {
	return !((u == delu && v == delv) || (v == delu && u == delv));
}

void dfs_d(int u) {
//	cerr << u << endl;
	vis[u] = true;
	cur.push_back(u);
	for (int i = 0; i < (int) g[u].size(); i++)
	if (!vis[g[u][i]] && notdel(u, g[u][i])) dfs_d(g[u][i]);
}

void loop() {
	for (int i = 0; i < n; i++)
		ans.push_back(INF);
	for (int i = 0; i < m; i++) {
		cur.clear();
		memset(vis, false, sizeof(vis));
		delu = edges[i].first;
		delv = edges[i].second;
//		cerr << delu << " " << delv << endl;
		dfs_d(1);
		if ((int) cur.size() == n && cur < ans) ans = cur;
//		for (int i = 0; i < n; i++) cerr << cur[i] << " "; cerr << endl;
	}
	for (int i = 0; i < n; i++)
		cout << ans[i] << " ";
	cout << endl;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int p, q;
		cin >> p >> q;
		link(p, q);
		link(q, p);
		edges[i] = make_pair(p, q);
	}
	for (int i = 1; i <= n; i++) 
		sort(g[i].begin(), g[i].end());
	
//	cerr << "calc" << endl;
	if (n == m) {
		loop();
	} else {
		tree();
	}
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #159.38 us172 KBAcceptedScore: 4

Testcase #264.9 us172 KBAcceptedScore: 4

Testcase #363.63 us172 KBAcceptedScore: 4

Testcase #495.75 us176 KBAcceptedScore: 4

Testcase #595.12 us176 KBAcceptedScore: 4

Testcase #6466.83 us272 KBAcceptedScore: 4

Testcase #7464.85 us276 KBAcceptedScore: 4

Testcase #8467.71 us280 KBAcceptedScore: 4

Testcase #9472.57 us264 KBAcceptedScore: 4

Testcase #10473.36 us260 KBAcceptedScore: 4

Testcase #112.341 ms644 KBAcceptedScore: 4

Testcase #122.336 ms680 KBAcceptedScore: 4

Testcase #132.326 ms692 KBAcceptedScore: 4

Testcase #142.335 ms644 KBAcceptedScore: 4

Testcase #152.334 ms720 KBAcceptedScore: 4

Testcase #1663.15 us176 KBAcceptedScore: 4

Testcase #1764.49 us176 KBAcceptedScore: 4

Testcase #18188.04 us184 KBAcceptedScore: 4

Testcase #19188.64 us184 KBAcceptedScore: 4

Testcase #2012.339 ms292 KBAcceptedScore: 4

Testcase #2112.427 ms292 KBAcceptedScore: 4

Testcase #2212.769 ms292 KBAcceptedScore: 4

Testcase #23636.905 ms728 KBAcceptedScore: 4

Testcase #24633.096 ms712 KBAcceptedScore: 4

Testcase #25638.044 ms700 KBAcceptedScore: 4


Judge Duck Online | 评测鸭在线
Server Time: 2020-08-05 15:18:37 | Loaded in 12 ms | Server Status
个人娱乐项目,仅供学习交流使用