NC21601. 出题人的无向图
描述
输入描述
输入文件开始为3个正整数n,m,kk
然后两行，每行n个正整数。
第一行为每个点的属性a[i]，
第二行为每个点的属性b[i]。
然后为m行，每行两个不相同的整数x,y表示m条边的端点(保证无重边，端点合法)
这之后为一个正整数q，表示询问个数。
接下来q行每行描述一个询问，
每行第一个数为V，第二个数为k，接下来k个数表示删去的点（不保证两两不同）
输出描述
输出文件共q行，每行一个整数，表示该次询问的答案。
若该次询问中所有点都被删掉，输出0
示例1
输入:
5 4 2 3 7 2 5 4 1 3 3 2 2 1 3 1 2 3 4 3 5 5 4 0 4 1 3 1 0 5 0 10 0
输出:
0 0 0 1 2
说明:
第一次询问，有1、3、5号点，它们之间有关联。C++(g++ 7.5.0) 解法, 执行用时: 775ms, 内存消耗: 90160K, 提交时间: 2022-11-16 18:28:42
#include<iostream>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
const int N=5e5+5;
int n,m,q,kk,p[N],ans[N],f[N],a[N],b[N],id[N];
multiset<int>Q;
vector<int>to[N],e[N];
map<int,int>S[N];
struct node{
int a,b,w;
bool operator <(node x){
return w<x.w;
}
}h[N];
struct Node{
int v,k,id;
bool operator <(Node x){
return v<x.v;
}
}t[N];
bool del[N];
int find(int x)
{
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
void add(int x,int c)
{
Q.erase(Q.find(f[x]));
if(S[x][c]%kk==0&&S[x][c]>0) f[x]--;
S[x][c]++;
if(S[x][c]%kk==0) f[x]++;
Q.insert(f[x]);
}
void merge(int l,int r)
{
if(to[l].size()>to[r].size()) swap(l,r);
p[l]=r;
for(int i:to[l])
{
to[r].push_back(i);
add(r,b[i]);
}
Q.erase(Q.find(f[l]));
}
bool cmp(int &x,int &y)
{
return a[x]<a[y];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>kk;
for(int i=1;i<=n;i++) cin>>a[i],id[i]=i;
sort(id+1,id+1+n,cmp);
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=1;i<=m;i++)
{
int l,r,w;
cin>>l>>r;
w=max(a[l],a[r]);
h[i]={l,r,w};
}
sort(h+1,h+1+m);
cin>>q;
for(int i=1;i<=q;i++)
{
int v,k,x;
cin>>v>>k;
t[i]={v,k,i};
for(int j=1;j<=k;j++) cin>>x,e[i].push_back(x);
}
sort(t+1,t+1+q);
for(int i=1;i<=n;i++) p[i]=i,to[i].push_back(i),Q.insert(0);
int cnt1=1,cnt2=1;
for(int i=1;i<=q;i++)
{
int v=t[i].v,k=t[i].k;
while(cnt1<=n&&a[id[cnt1]]<=v)
{
int u=find(id[cnt1]);
add(u,b[id[cnt1]]);
cnt1++;
}
while(cnt2<=m&&h[cnt2].w<=v)
{
int l=find(h[cnt2].a),r=find(h[cnt2].b);
if(l!=r) merge(l,r);
cnt2++;
}
for(int j:e[t[i].id])
{
int u=find(j);
if(!del[u])
{
del[u]=1;
Q.erase(Q.find(f[u]));
}
}
if(Q.size()) ans[t[i].id]=*Q.rbegin();
else ans[t[i].id]=0;
for(int j:e[t[i].id])
{
int u=find(j);
if(del[u])
{
del[u]=0;
Q.insert(f[u]);
}
}
}
for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
return 0;
}
C++14(g++5.4) 解法, 执行用时: 1427ms, 内存消耗: 81036K, 提交时间: 2019-01-20 20:29:16
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
const int maxq = 5e5+5;
int n, m, kk;
int a[maxn], b[maxn], a_id[maxn];
int fa[maxn], sz[maxn];
int cnt[maxn];
map<int, int> mp[maxn];
vector<int> G[maxn];
multiset<int>s;
struct qnode{
int id;
int v;
vector<int>k;
bool operator < (const qnode &rhs) const {
return v < rhs.v;
}
}query[maxq];
int ans[maxq];
bool in_map[maxn];
bool deleted[maxn];
int find(int x) {
if (fa[x] == x)
return x;
else
return fa[x] = find(fa[x]);
}
void combine(int x, int y) {
if (sz[x] > sz[y])
swap(x, y);
sz[y] += sz[x];
fa[x] = y;
s.erase(s.find(cnt[x]));
s.erase(s.find(cnt[y]));
for (auto status : mp[x]) {
int v_in_x = status.second;
int v_in_y = mp[y][status.first];
if (v_in_y)
cnt[y] -= ((v_in_y)%kk == 0) ? 1 : 0;
mp[y][status.first] += v_in_x;
if ((v_in_x + v_in_y) % kk == 0)
cnt[y]++;
}
s.insert(cnt[y]);
}
void M_insert(int id) {
in_map[id] = true;
s.insert(cnt[id]);
for (int nxt : G[id]) {
if (in_map[nxt] && find(nxt) != find(id)) {
combine(find(nxt), find(id));
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &kk);
for (int i = 1; i <= n; ++i)
scanf("%d", a+i);
for (int i = 1; i <= n; ++i)
scanf("%d", b+i);
int x, y;
while (m--) {
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
int numq;
scanf("%d", &numq);
int knum, kval;
for (int i = 1; i <= numq; ++i) {
scanf("%d%d", &query[i].v, &knum);
while (knum--) {
scanf("%d", &kval);
query[i].k.push_back(kval);
}
query[i].id = i;
}
sort(query+1, query+1+numq);
for (int i = 1; i <= n; ++i)
a_id[i] = i;
sort(a_id+1, a_id+1+n, [&](int x, int y){return a[x] < a[y];});
for (int i = 1; i <= n; ++i) {
fa[i] = i;
sz[i] = 1;
mp[i][b[i]] = 1;
cnt[i] = (kk==1)?1:0;
}
s.insert(0);
int cur = 0;
for (int i = 1; i <= numq; ++i){
while (cur < n && a[a_id[cur+1]] <= query[i].v) {
cur++;
M_insert(a_id[cur]);
}
for (auto p :query[i].k) {
if (in_map[p] && !deleted[find(p)]) {
s.erase(s.find(cnt[find(p)]));
deleted[find(p)] = true;
}
}
ans[query[i].id] = *(--s.end());
for (auto p : query[i].k) {
if (in_map[p] && deleted[find(p)]) {
deleted[find(p)] = false;
s.insert(cnt[find(p)]);
}
}
}
for (int i = 1; i <= numq; ++i) {
printf("%d\n", ans[i]);
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 1206ms, 内存消耗: 70776K, 提交时间: 2019-06-01 14:50:04
#include<bits/stdc++.h>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int mx = 2e5 + 10;
int n,m,K,a[mx],b[mx];
int ret[mx*3],fa[mx],cnt[mx];
multiset <int> st;
vector <int> g[mx];
map <int,int> mp[mx];
int find(int x){
return x==fa[x]? x:fa[x]=find(fa[x]);
}
struct node{
int p,v;
bool operator < (node A)const{return v < A.v;}
}s[mx];
struct edge{
int v,p;
vector<int> r;
bool operator < (edge A)const{return v < A.v;}
}e[mx*3];
void merge(int x,int y){
x = find(x);
y = find(y);
if(x==y) return ;
st.erase(st.find(cnt[x]));
st.erase(st.find(cnt[y]));
if(mp[x].size()<mp[y].size()) swap(x,y);
fa[y] = x;
for(auto it:mp[y]){
if(mp[x][it.fi]&&mp[x][it.fi]%K==0) cnt[x]--;
mp[x][it.fi] += it.se;
if(mp[x][it.fi]%K==0) cnt[x]++;
}
st.insert(cnt[x]);
}
void add(int p){
fa[p] = p;
mp[p][b[p]] = 1;
if(K==1) cnt[p] = 1;
st.insert(cnt[p]);
for(int v:g[p]) if(fa[v]){
merge(p,v);
}
}
int solve(int p,int x){
while(p<=n&&s[p].v<=e[x].v) add(s[p++].p);
int siz = e[x].r.size();
set <int> s1;
for(int i=0;i<siz;i++) if(fa[e[x].r[i]])
s1.insert(find(e[x].r[i]));
for(auto it:s1)
st.erase(st.find(cnt[it]));
if(st.empty()) ret[e[x].p] = 0;
else ret[e[x].p] = *st.rbegin();
for(auto it:s1) st.insert(cnt[it]);
return p;
}
int main(){
scanf("%d%d%d",&n,&m,&K);
for(int i=1;i<=n;i++){
scanf("%d",a+i);
s[i].v = a[i],s[i].p = i;
}
for(int i=1;i<=n;i++) scanf("%d",b+i);
int u,v,q;
while(m--){
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
scanf("%d",&q);
for(int i=1;i<=q;i++){
scanf("%d",&e[i].v);
e[i].p = i;
scanf("%d",&u);
for(int j=1;j<=u;j++){
scanf("%d",&v);
e[i].r.push_back(v);
}
}
sort(s+1,s+1+n);
sort(e+1,e+1+q);
for(int i=1,p=1;i<=q;i++)
p = solve(p,i);
for(int i=1;i<=q;i++) printf("%d\n",ret[i]);
return 0;
}