Submission #1092187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092187		onlk97	Garden (JOI23_garden)	C++14	100 / 100	2654 ms	12552 KiB

garden

#include <bits/stdc++.h>
using namespace std;
struct DSU{
    vector <int> pa,siz;
    void init(int n){
        for (int i=0; i<=n; i++){
            pa.push_back(i);
            siz.push_back(1);
        }
    }
    int prt(int n){
        if (pa[n]==n) return n;
        return pa[n]=prt(pa[n]);
    }
    void unn(int u,int v){
        u=prt(u); v=prt(v);
        if (u==v) return;
        if (siz[u]<siz[v]) swap(u,v);
        pa[v]=u;
        siz[u]+=siz[v];
    }
    int getsiz(int u){
        return siz[prt(u)];
    }
};
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,m,d;
    cin>>n>>m>>d;
    int p[n+1],q[n+1],r[m+1],s[m+1];
    for (int i=1; i<=n; i++) cin>>p[i]>>q[i];
    for (int i=1; i<=m; i++) cin>>r[i]>>s[i];
    int cost[d];
    for (int i=0; i<d; i++) cost[i]=-1;
    for (int i=1; i<=n; i++) cost[q[i]]=1e9;
    for (int i=1; i<=m; i++) cost[s[i]]=max(cost[s[i]],r[i]+1);
    bool done[d];
    int ans=d*d;
    set <int> f;
    for (int i=1; i<=n; i++){
        f.insert(p[i]);
        f.insert(p[i]+d);
    }
    vector <int> ins[d];
    for (int i=1; i<=m; i++) ins[r[i]].push_back(s[i]);
    for (int i=0; i<d; i++){
        if (i){
            for (int j:ins[i-1]) cost[j]=max(cost[j],i+d);
        }
        vector <pair <int,int> > v;
        for (int j=0; j<d; j++) v.push_back({cost[j]-i,j});
        sort(v.begin(),v.end());
        int height=0;
        auto it=f.lower_bound(i+d);
        height=*(--it)-i+1;
        DSU dsu;
        dsu.init(d);
        for (int j=0; j<d; j++) done[j]=0;
        int gap=0;
        ans=min(ans,height*d);
        for (auto j:v){
            height=max(height,j.first);
            if (height>=d+10) break;
            int prv=(j.second+d-1)%d;
            if (done[prv]) dsu.unn(prv,j.second);
            int nxt=(j.second+1)%d;
            if (done[nxt]) dsu.unn(j.second,nxt);
            gap=max(gap,dsu.getsiz(j.second));
            done[j.second]=1;
            ans=min(ans,height*(d-gap));
        }
    }
    cout<<ans<<'\n';
}

• Subtask 1: 15 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 30 / 30
• Subtask 6: 25 / 25