悬小号1关 简单题求卡常
查看原帖
悬小号1关 简单题求卡常
1013955
1234567890sjx楼主2024/9/18 20:57
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
// #define int long long
#define F(i,x,y) for(int i=x;i<=y;++i)
#define G(i,x,y) for(int i=x;i>=y;--i)
#define FD(i,x,y) for(int i=x;i*i<=y;++i)
#define GD(i,x,y) for(int i=x;i*i>=y;--i)
#define adde(x,y) z[x].eb(y);
#define Adde(x,y) z[x].eb(y),z[y].eb(x);
#define addew(x,y,w) z[x].eb(y,w)
#define Addew(x,y,w) z[x].eb(y,w),z[y].eb(x,w)
#define FIMX(X) memset(X,0x3f,sizeof X)
#define FIMI(X) memset(X,-0x3f,sizeof X)
#define FI0(X) memset(X,0,sizeof X)
#define FIN(X) memset(X,-1,sizeof X)
#define rng(X) X.begin(),X.end()
#define PII pair<int,int>
#define PDD pair<double,double>
#define PIII tuple<int,int,int>
#define VI vector<int>  
#define VII vector<PII>
#define VID vector<pair<int,double>>
#define VDD vector<PDD>
using namespace std;
const int N=500100;
struct qwq{
    int x,id;
    bool operator>(const qwq&r)const{
        return x<r.x;
    }
}a[N],b[N],c[N],d[N];
int ra[N],rb[N],rc[N],rd[N];
struct Tup{
    int a,b,c,d;
    bool operator<(const Tup&r)const{
        int sc1=::a[a].x+::b[b].x+::c[c].x+::d[d].x;
        int sc2=::a[r.a].x+::b[r.b].x+::c[r.c].x+::d[r.d].x;
        if(sc1>sc2)return 1;
        if(sc1<sc2)return 0;
        return a<r.a||a==r.a&&b<r.b||a==r.a&&b==r.b&&c<r.c||a==r.a&&b==r.b&&c==r.c&&d<r.d;
    }
};
set<Tup>se;
void solve(unsigned int __testid=1){
    int n1,n2,n3,n4;
    cin>>n1>>n2>>n3>>n4;
    F(i,1,n1)cin>>a[i].x,a[i].id=i;
    F(i,1,n2)cin>>b[i].x,b[i].id=i;
    F(i,1,n3)cin>>c[i].x,c[i].id=i;
    F(i,1,n4)cin>>d[i].x,d[i].id=i;
    sort(a+1,a+n1+1,greater<qwq>());
    sort(b+1,b+n2+1,greater<qwq>());
    sort(c+1,c+n3+1,greater<qwq>());
    sort(d+1,d+n4+1,greater<qwq>());
    F(i,1,n1)ra[a[i].id]=i;
    F(i,1,n2)rb[b[i].id]=i;
    F(i,1,n3)rc[c[i].id]=i;
    F(i,1,n4)rd[d[i].id]=i;
    int m1;cin>>m1;set<PII>se1;
    F(i,1,m1){int x,y;cin>>x>>y;se1.insert({ra[x],rb[y]});}
    int m2;cin>>m2;set<PII>se2;
    F(i,1,m2){int x,y;cin>>x>>y;se2.insert({rb[x],rc[y]});}
    int m3;cin>>m3;set<PII>se3;
    F(i,1,m3){int x,y;cin>>x>>y;se3.insert({rc[x],rd[y]});}
    priority_queue<Tup>tup;
    tup.push({1,1,1,1});
    while(tup.size()){
        auto [A,B,C,D]=tup.top();tup.pop();
        // cout<<"You have no "<<A<<' '<<B<<' '<<C<<' '<<D<<'\n';
        if(!se1.count({A,B})&&!se2.count({B,C})&&!se3.count({C,D})){
            int score=a[A].x+b[B].x+c[C].x+d[D].x;
            cout<<score<<'\n';
            return;
        }
        if(D<n4&&!se.count({A,B,C,D+1}))tup.push({A,B,C,D+1}),se.insert({A,B,C,D+1});
        if(C<n3&&!se.count({A,B,C+1,D}))tup.push({A,B,C+1,D}),se.insert({A,B,C+1,D});
        if(B<n2&&!se.count({A,B+1,C,D}))tup.push({A,B+1,C,D}),se.insert({A,B+1,C,D});
        if(A<n1&&!se.count({A+1,B,C,D}))tup.push({A+1,B,C,D}),se.insert({A+1,B,C,D});
    }
    cout<<"-1\n";
}
int32_t main(){
    // freopen("d.in","r",stdin);
    // freopen("d.out","w",stdout);
    // ios_base::sync_with_stdio(0) ;
    // cin.tie(nullptr);
    int T;
    T=1;
    // cin>>T;
    F(_,1,T)
        solve(_);  
    return 0;
}

//84076361542
//3487268488

TLE on test #8

2024/9/18 20:57
加载中...