Submission #1092174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092174		onlk97	Garden (JOI23_garden)	C++14	60 / 100	3076 ms	4496 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];
    bool done[d];
    int ans=d*d;
    for (int i=0; i<d; i++){
        for (int j=0; j<d; j++) cost[j]=-1;
        for (int j=1; j<=n; j++) cost[q[j]]=1e9;
        for (int j=1; j<=m; j++) cost[s[j]]=max(cost[s[j]],(r[j]-i+d)%d+1);
        vector <pair <int,int> > v;
        for (int j=0; j<d; j++) v.push_back({cost[j],j});
        sort(v.begin(),v.end());
        int height=0;
        for (int j=1; j<=n; j++) height=max(height,(p[j]-i+d)%d+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: 0 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 30 / 30
• Subtask 6: 0 / 25