Grakn Forces

Grakn Forces

CF1408D Searchlights

大菜鸡大水题又又做不出来了

做法见注释

//Proudly using c++11 by gwt
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//#define endl '
'
#define count2(x) __builtin_popcount(x)
#define countleadingzero(x) __builtin_clz(x)
#define debug(x) cerr << #x << " = " << x << endl;
inline ll read(){//not solve LLONG_MIN LMAX=9,223,372,036,854,775,807
    ll s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0' && ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int main(){
	int n,m;
	cin>>n>>m;
	vector<pii>nums(n);
	for(int i=0;i<n;++i)
	cin>>nums[i].fi>>nums[i].se;
	vector<int>dis(1e6+1);
	//做法复杂度为O(nm+1e6) 
	for(int i=0;i<m;++i){
		int p,q;
		cin>>p>>q;
		for(int j=0;j<n;++j){
			if(p>=nums[j].fi){
				//更新当整体增加x时 越过纵坐标边界的距离需要的最大值 
				dis[p-nums[j].fi]=max(dis[p-nums[j].fi],q-nums[j].se+1);
			}
		}
	}
	int maxy=0;
	int ans=INT_MAX;
	for(int i=1e6;i>=0;--i){
		//欲要满足更小的x 就需要更大的y 
		maxy=max(maxy,dis[i]);
		ans=min(ans,i+maxy);//取得所有合法条件下的最小值
	}
	
	cout<<ans;
//	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	return 0;
}

CF1408E Avoid Rainbow Cycles

大菜鸡大水题又又做不出来了

做法见注释

//by gwt Proudly powered by C++17
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;
//Maximum Spanning Tree
constexpr int maxnm=1e5*2+1;
int father[maxnm];
int a[maxnm];
int b[maxnm];
inline int find(int x){
	return father[x]==x?x:father[x]=find(father[x]);
}
struct node{
	ll u,v,w;
};
bool operator<(const node &a,const node &b){
	return a.w<b.w;
}
priority_queue<node>qn;
int main(){
	//考虑在没有循环的情况下最小化费用
	//等价于留下费用最大的边
	//转化为最大生成树
	//对ai->bj的边权为ai+bj;
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=m+n;++i)
	father[i]=i;
	for(int i=1;i<=m;++i)
	cin>>a[i];
	for(int i=1;i<=n;++i)
	cin>>b[i];
	ll ans=0;
	for(int i=1;i<=m;++i){
		int sn;
		cin>>sn;
		for(int j=1;j<=sn;++j){
			int vertex;
			cin>>vertex;
			ll w=(ll)a[i]+b[vertex];
			ans+=a[i]+b[vertex];
			qn.push({i,m+vertex,w});
		}
	}
	ll mst=0;
	while(!qn.empty()){
		auto i=qn.top();
		qn.pop();
		int fa=find(i.u);
		int fb=find(i.v);
		if(fa!=fb){
			mst+=i.w;
			father[fa]=fb;
		}
	}
	cout<<ans-mst;
	return 0;
}