2019CCPC 哈尔滨 E - Exchanging Gifts (离散化+fastIO+bfs)
解析:
按照2 x y建有向边,就可得到DAG,然后做一个bfs,算权值,就可以了。
但这样一般会T,还需要离散化和fastIO,用map复杂度太高了。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <iostream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
const int N = 1e6+10;
typedef long long ll;
vector<int> edge[N];
int a[N];
int mark[N];
int deg[N];
int len[N];
ll mp[N];
ll val[N];
int mq[N];
int b[N];
#define typeinput int
#define IO ios::sync_with_stdio(false);cin.tie(0)
//fastIO1
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(typeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}
//fastIO2
namespace fastIO{
#define BUF_SIZE 1000000
bool IOerror=0;
inline char nc(){
static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend = buf + BUF_SIZE;
if(p1==pend){
p1=buf;
pend=buf+fread(buf,1,BUF_SIZE,stdin);
if(pend==p1){
IOerror = 1;
return -1;
}
}
return *p1++;
}
inline bool blank(char ch){
return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
}
inline void read(int &x){
char ch;
while(blank(ch=nc()));
if(IOerror) return ;
for(x=ch-'0';(ch=nc())>='0'&&ch<='9';x=x*10+ch-'0');
}
#undef BUF_SIZE
}
//toposort
void bfs(int s,int n)
{
int head,tail;
head=tail=0;
for(int i=1;i<=n;i++)
{
if(deg[i]==0) mq[tail++]=i;
}
val[s]=1;
while(head<tail)
{
int u=mq[head];
head++;
for(auto v:edge[u])
{
val[v]+=val[u];
deg[v]--;
if(deg[v]==0)
mq[tail++]=v;
}
}
}
int main()
{
int t;
read(t);
while(t--)
{
int n;
int cnt=0;
int id;
read(n);
for(int i=1;i<=n;i++)
{
deg[i]=0; //2 x y (x,y<=i-1)
val[i]=0;
edge[i].clear();
read(id);
if(id==1)
{
int k;
read(k);
mark[i]=cnt;
len[i]=k;
for(int j=1;j<=k;j++)
{
int tmp;
read(tmp);
a[cnt++]=tmp;
}
}
else
{
mark[i]=-1;
len[i]=0;
int x,y;
read(x);
read(y);
edge[i].push_back(x);
edge[i].push_back(y);
deg[x]++;
deg[y]++;
}
}
//离散化
for(int i=0;i<cnt;i++) b[i]=a[i];
sort(b,b+cnt);
int cm = unique(b,b+cnt)-b;
for(int i=0;i<cnt;i++) a[i]=lower_bound(b,b+cm,a[i])-b;
//
ll ans=0;
for(int i=0;i<cm;i++) mp[i]=0;
if(id==1)
{
ll maxx = 0;
for(int i=mark[n];i<mark[n]+len[n];i++)
{
mp[a[i]]++;
if(mp[a[i]]>maxx) maxx = mp[a[i]];
}
if(maxx>=len[n]/2+1)
ans=1ll*(len[n]-maxx)*2;
else
ans=len[n];
}
else
{
bfs(n,n);
ll maxx =0;
ll tot = 0;
for(int i=1;i<=n;i++)
{
if(len[i]==0||val[i]==0) continue;
tot += 1ll*len[i]*val[i];
for(int j=mark[i];j<mark[i]+len[i];j++)
{
mp[a[j]]+=val[i];
if(mp[a[j]]>maxx) maxx = mp[a[j]];
}
}
if(maxx>=tot/2+1)
ans = 1ll*(tot-maxx)*2;
else
ans = tot;
}
printf("%lld\n",ans);
}
}