QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#233673#3026. Little Wormjerzyk#AC ✓360ms15068kbC++204.3kb2023-10-31 21:16:152023-10-31 21:16:16

Judging History

你现在查看的是最新测评结果

  • [2023-10-31 21:16:16]
  • 评测
  • 测评结果:AC
  • 用时:360ms
  • 内存:15068kb
  • [2023-10-31 21:16:15]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define st first
#define nd second
#define pb push_back
const int N = 100 * 1000 + 7;
bool od[N];
vector<int> ed[N], pth, cura;
int wys[N], mwy[N], wh[N], oj[N];

bool DFSP(int v, int tar)
{
	od[v] = true;
	if(v == tar)
	{pth.pb(v); return true;}
	for(int i = 0; i < (int)ed[v].size(); ++i)
	{
		if(od[ed[v][i]]) continue;
		if(DFSP(ed[v][i], tar))
		{
			pth.pb(v);
			return true;
		}
	}
	return false;
}

void DFS(int v)
{
	mwy[v] = wys[v]; wh[v] = v;
	for(int i = 0; i < (int)ed[v].size(); ++i)
	{
		if(wys[ed[v][i]]) continue;
		wys[ed[v][i]] = wys[v] + 1; oj[ed[v][i]] = v;
		DFS(ed[v][i]);
		if(mwy[ed[v][i]] > mwy[v])
		{
			mwy[v] = mwy[ed[v][i]];
			wh[v] = ed[v][i];
		}
	}
}

inline void Pth(int a, int b, int n)
{
	pth.clear();
	DFSP(b, a);
	for(int i = 1; i <= n; ++i) od[i] = false;
}

void DoA(int a, int b, int tar, int d, int n)
{
	cura.clear();
	wys[tar] = 1; DFS(tar);
	while(cura.size() <= 10 * n)
	{
		int pa = a, pb = b;
		if(b == tar || a == tar) break;
		int il = mwy[a] - wys[a] + 1, cur = b, g = 0;
		for(int i = 1; i <= il; ++i)
		{
			if(mwy[cur] > mwy[g]) g = cur;
			cur = oj[cur];
		}
		if(mwy[a] >= d) g = tar;
		while(b != g)
		{
			cura.pb(wh[a]);
			a = wh[a]; b = oj[b];
		}
		if(b == tar || a == tar) break;

		il = mwy[b] - wys[b] + 1, cur = a, g = 0;
		for(int i = 1; i <= il; ++i)
		{
			if(mwy[cur] > mwy[g]) g = cur;
			cur = oj[cur];
		}
		if(mwy[b] >= d) g = tar;
		while(a != g)
		{
			cura.pb(wh[b]);
			b = wh[b]; a = oj[a];
		}
		if(b == tar || a == tar) break;
		if(pa == a && pb == b)
		{
			cura.pb(-1);
			return;
		}
	}
	for(int i = 1; i <= n; ++i)
	{
		wys[i] = 0; oj[i] = 0;
	}
}

int DoR(int a, int b, int tar, int d, int n)
{
	for(int i = 1; i <= n; ++i)
	{
		wys[i] = 0; oj[i] = 0;
	}
	cura.clear();
	wys[tar] = 1; DFS(tar);
	while(cura.size() <= 10 * n)
	{
		//cout << "p " << a << " " << b << "\n";
		int pa = a, pb = b;
		if(b == tar || a == tar) break;
		int il = mwy[a] - wys[a] + 1, cur = b, g = b;
		for(int i = 1; i <= il; ++i)
		{
			if(mwy[cur] > mwy[g]) g = cur;
			cur = oj[cur];
		}
		if(mwy[a] >= d) g = tar;
		while(b != g)
		{
			cura.pb(b);
			a = wh[a]; b = oj[b];
		}
		if(b == tar || a == tar) break;

		il = mwy[b] - wys[b] + 1; cur = a; g = a;
		for(int i = 1; i <= il; ++i)
		{
			if(mwy[cur] > mwy[g]) g = cur;
			cur = oj[cur];
		}
		if(mwy[b] >= d) g = tar;
		//cout << g << " " << mwy[b] << "\n";
		while(a != g)
		{
			cura.pb(a);
			b = wh[b]; a = oj[a];
		}
		if(b == tar || a == tar) break;
		if(pa == a && pb == b) return -1;
	}
	for(int i = 1; i <= n; ++i)
	{
		wys[i] = 0; oj[i] = 0;
	}
	reverse(cura.begin(), cura.end());
	if(a == tar) return b;
	return a;
}


void Solve() 
{
	int n, a, b, c, d, x, y, di;
	int dok;
	vector<int> ans, pab, pcd, pac;
	cin >> n;
	for(int i = 1; i <= n; ++i)
	{
		wys[i] = 0; od[i] = false;
		ed[i].clear();
	}
	for(int i = 1; i < n; ++i)
	{
		cin >> a >> b;
		ed[a].pb(b); ed[b].pb(a);
	}
	cin >> a >> b;
	cin >> c >> d;
	Pth(a, b, n); pab = pth;
	Pth(c, d, n); pcd = pth;
	Pth(a, c, n); pac = pth;
	for(int i = 0; i < (int)min(pab.size(), pac.size()); ++i)
		if(pab[i] == pac[i]) x = pab[i];
	reverse(pac.begin(), pac.end());
	for(int i = 0; i < (int)min(pcd.size(), pac.size()); ++i)
		if(pcd[i] == pac[i]) y = pcd[i];
	reverse(pac.begin(), pac.end());
	di = pab.size();
	DoA(a, b, x, di, n);
	ans = cura;
	dok = DoR(c, d, y, di, n);
	//cout << "\n " << dok << " " << x << " " << y << "\n";
	if(cura.size() + ans.size() > 10 * n || dok == -1 || (ans.size() > 0 && ans.back() == -1))
	{
		cout << -1 << "\n";
		return;
	}
	Pth(x, dok, n);
	for(int i = 1; i < (int)pth.size(); ++i) ans.pb(pth[i]);
	for(int i = 0; i < (int)cura.size(); ++i) ans.pb(cura[i]);
	if(ans.size() > 10 * n)
	{
		cout << -1 << "\n";
		return;
	}
	cout << ans.size() << "\n";
	for(int i = 0; i < (int)ans.size(); ++i)
		cout << ans[i] << " ";
	cout << "\n";
	for(int i = 1; i <= n; ++i)
	{
		wys[i] = 0; od[i] = false;
		ed[i].clear();
	}
	pth.clear(); cura.clear();
}

int main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int _=1;
	cin >> _;
	while(_--) Solve();
}

详细

Test #1:

score: 100
Accepted
time: 156ms
memory: 7424kb

input:

7000
92
50 58
92 77
24 21
57 67
63 78
40 90
57 92
73 45
87 85
68 43
11 46
87 7
70 9
62 25
45 80
76 57
49 86
10 48
10 83
88 82
7 82
5 31
16 42
75 84
33 6
28 2
56 5
81 64
11 33
17 38
35 63
4 31
54 90
86 65
23 91
15 30
66 71
53 37
48 27
69 59
67 32
92 50
71 8
74 52
79 75
25 88
41 55
40 39
60 47
49 12
4...

output:

79
54 7 87 85 89 13 44 19 91 23 61 52 74 26 18 29 68 43 83 10 48 27 55 41 82 88 25 62 8 71 66 70 9 3 77 51 46 11 33 6 79 75 84 42 20 2 28 56 5 31 4 92 50 58 37 53 22 14 16 15 30 78 63 35 57 76 80 45 73 81 36 17 38 67 47 60 64 1 32 
79
51 60 48 90 37 10 20 45 46 32 4 75 50 43 68 26 87 55 63 3 86 54 2...

result:

ok OK!

Test #2:

score: 0
Accepted
time: 194ms
memory: 6612kb

input:

470
743
429 611
226 347
611 87
507 72
23 589
673 27
563 260
567 724
316 41
89 470
292 80
11 218
139 32
145 422
394 296
706 552
581 20
358 491
632 40
390 284
224 506
141 491
541 202
533 669
122 273
421 350
566 607
275 205
126 352
195 491
469 445
259 426
624 547
135 339
503 325
639 444
677 53
459 425
...

output:

-1
9
373 412 781 163 492 383 20 96 846 
3571
3587 1715 1536 1705 885 790 319 1148 2981 1218 116 560 2830 3652 2794 1953 736 1502 672 2134 2464 3230 1404 606 2980 3503 3062 2266 2466 3461 2903 2504 362 329 3563 1208 2372 767 1960 2941 294 557 1797 1557 2735 2806 3537 940 520 479 3391 3610 2819 171 29...

result:

ok OK!

Test #3:

score: 0
Accepted
time: 360ms
memory: 15068kb

input:

11
88832
31434 32960
21975 48728
73507 72853
8790 28585
34700 9499
84885 4809
17607 74921
38812 7277
15324 70994
21922 45093
27594 4262
73567 70888
34197 37341
5364 29062
72260 6143
40230 15118
13890 40327
26144 60801
18852 11719
35653 12248
60905 79198
69712 1971
18796 12498
49133 34898
84942 72077...

output:

88411
23337 34664 13391 11058 9943 16165 28102 21488 25850 30444 60 71581 53549 80422 49420 32241 13254 68001 38263 66843 30309 55824 27575 10732 6658 27026 36977 50108 26722 38490 10127 51757 49701 78692 56502 53233 82620 10595 36902 3429 50559 66459 30132 81728 82615 74409 27123 50368 17741 20437 ...

result:

ok OK!