比赛 |
2024暑假C班集训E |
评测结果 |
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWEEEEEEEEEEA
|
题目名称 |
部落冲突 |
最终得分 |
60 |
用户昵称 |
liuyiche |
运行时间 |
12.402 s |
代码语言 |
C++ |
内存使用 |
16.15 MiB |
提交时间 |
2024-07-14 11:46:32 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int n, m, cnt = 0;
vector<int> c(100005,0);
bool p[6005][6005];
struct node
{
vector<int> nxt;
};
vector<node> v(300005);
vector<P> x(300005);
bool vis[6005];
int f[6005];
int Lowbit (int x)
{
return x&(-x);
}
void Add (int a, int b)
{
for (int i = a; i <= n; i+=Lowbit(i))
c[i] += b;
}
int Sum (int a, int b)
{
int suma = 0, sumb = 0;
for (int i = a-1; i > 0; i-=Lowbit(i))
suma += c[i];
for (int i = b; i > 0; i-=Lowbit(i))
sumb += c[i];
return sumb-suma;
}
inline bool dfs(int step, int to)
{
if(step == to)
return true;
if(f[step] != -1)
return f[step];
vis[step] = 1;
bool ans = 0;
for(int i = 0; i < v[step].nxt.size(); ++i)
if(p[step][v[step].nxt[i]] == 0 && vis[v[step].nxt[i]] == 0)
ans = max(ans,dfs(v[step].nxt[i],to));
vis[step] = 0;
return f[step] = ans;
}
int main()
{
freopen("lct.in","r",stdin);
freopen("lct.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i < n; ++i)
{
int x, y;
cin >> x >> y;
v[x].nxt.push_back(y);
v[y].nxt.push_back(x);
}
if(n > 6000)
{
for(int i = 1; i <= m; ++i)
{
char ch;
cin >> ch;
if(ch == 'Q')
{
int x, y;
cin >> x >> y;
if(x > y)
swap(x,y);
if(Sum(x,y-1) == 0)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
}
else if(ch == 'C')
{
cnt++;
cin >> x[cnt].first >> x[cnt].second;
Add(min(x[cnt].first,x[cnt].second),1);
}
else
{
int idx;
cin >> idx;
Add(min(x[idx].first,x[idx].second),-1);
}
}
return 0;
}
for(int i = 1; i <= m; ++i)
{
char ch;
cin >> ch;
if(ch == 'Q')
{
int x, y;
cin >> x >> y;
for(int i = 1; i <= n; ++i)
f[i] = -1;
if(dfs(x,y) == true)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
}
else if(ch == 'C')
{
cnt++;
cin >> x[cnt].first >> x[cnt].second;
p[x[cnt].first][x[cnt].second] = 1;
p[x[cnt].second][x[cnt].first] = 1;
}
else
{
int idx;
cin >> idx;
p[x[idx].first][x[idx].second] = 0;
p[x[idx].second][x[idx].first] = 0;
}
}
return 0;
}