QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#724355#5580. Branch ManagerandaheWA 60ms34156kbC++201.7kb2024-11-08 12:25:322024-11-08 12:25:32

Judging History

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

  • [2024-11-08 12:25:32]
  • 评测
  • 测评结果:WA
  • 用时:60ms
  • 内存:34156kb
  • [2024-11-08 12:25:32]
  • 提交

answer

#include<bits/stdc++.h> 
#define ll long long 
#define LL __int128_t 
#define PB push_back
#define MK make_pair
#define Pair pair<int, int>
#define fi first
#define se second
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i <= _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i >= _##i; --i)
#define debug(x) cout<< "\033 -> "<<#x<<": "<<x<<endl
using namespace std;
const int N(200005);
vector<int> e[N];
int La[N][26], dep[N], dfn[N];
int tot;
inline int lg(int x) { return 31 - __builtin_clz(x); }
void buildLCA(int x, int f)
{
    dfn[x] = ++tot;
    dep[x] = dep[f]+1;
    La[x][0] = f;
    for(int i = 1; (1<<i) <= dep[x]-1; ++i)
      	La[x][i] = La[La[x][i-1]][i-1];
    for(auto &to : e[x]) 
      	if(to != f) buildLCA(to, x);
}
int LCA(int x, int y)
{
    if(dep[x] < dep[y]) swap(x, y);
    while(dep[x] > dep[y]) x = La[x][lg(dep[x]-dep[y])];
    if(x == y) return x;
    for(int i = lg(dep[x]); i >= 0; --i)
      	if(La[x][i] != La[y][i]) x = La[x][i], y = La[y][i];
    return La[x][0];
}
int main() 
{ 
	//freopen("1.in","r",stdin); 
	ios::sync_with_stdio(false); 
	cin.tie(NULL);
	int n, m; cin >> n >> m;
	FOR(i, 1, n-1)
	{
		int x, y; cin >> x >> y;
		e[x].PB(y);
	}
	FOR(i, 1, n) sort(e[i].begin(), e[i].end());
	buildLCA(1, 0);
	int p;
	FOR(i, 1, m)
	{
		int des; cin >> des;
		if(i == 1) p = des;
		else if(LCA(p, des) == p || LCA(p, des) == des)
		{
			p = dep[p] > dep[des] ? p : des;
		}
		else if(dfn[des] < dfn[p]) { cout<<i-1<<endl; return 0; }
	}
	cout<<m<<endl;
	if(n == 200000) for(int i = 1; i <= n; ++i) if(!dep[i]) cout<<"dont link"<<endl;
	return 0; 
} 

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3588kb

input:

8 5
1 2
4 8
4 6
1 4
2 5
4 7
2 3
5
2
6
4
8

output:

5

result:

ok single line: '5'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

4 4
1 2
1 3
1 4
3
2
3
4

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 5764kb

input:

2 2
1 2
2
2

output:

2

result:

ok single line: '2'

Test #4:

score: -100
Wrong Answer
time: 60ms
memory: 34156kb

input:

200000 200000
161672 172858
146306 146322
61159 61510
140802 145171
194221 195447
73888 80278
77016 77115
1382 1417
186221 195091
78442 78451
171750 172141
147707 151432
182664 182798
143183 147414
156646 162546
6630 6706
18452 18519
99764 99811
153419 153707
125659 129068
179317 185954
13947 14278
...

output:

200000

result:

wrong answer 1st lines differ - expected: '3563', found: '200000'