Submission #810624

#	Time	Username	Problem	Language	Result	Execution time	Memory
810624		Theo830	Garden (JOI23_garden)	C++17	100 / 100	2065 ms	9912 KiB

garden

#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i = a;i < b;i++)
#define ll int
#define ii pair<ll,ll>
#define pb push_back
#define F first
#define S second
ll par[5005];
ll l[5005];
ll r[5005];
ll find_par(ll x){
    if(par[x] == x){
        return x;
    }
    return par[x] = find_par(par[x]);
}
void enose(ll p1,ll p2){
    par[p1] = p2;
    l[p2] = l[p1];
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,m,d;
    cin>>n>>m>>d;
    ll p[n],q[n];
    ll exo[d] = {0};
    bool ip[d] = {0};
    vector<ll> adj[d];
    vector<ll>w;
    bool ex[d] = {0};
    f(i,0,n){
        cin>>p[i]>>q[i];
        ip[q[i]] = 1;
        exo[p[i]]++;
        ex[q[i]] = 1;
        w.pb(q[i]);
    }
    ll R[m],s[m];
    f(i,0,m){
        cin>>R[i]>>s[i];
        adj[s[i]].pb(R[i]);
        ex[s[i]] = 1;
        w.pb(s[i]);
    }
    f(i,0,d){
        sort(adj[i].begin(),adj[i].end());
        unique(adj[i].begin(),adj[i].end());
    }
    ll ans = d * d;
    ll Mini = d;
    sort(w.begin(),w.end());
    unique(w.begin(),w.end());
    f(i,0,(ll)w.size()-1){
        Mini = min(Mini,d - (w[i+1] - w[i] - 1));
    }
    Mini = min(Mini,w.back() - w[0] + 1);
    ll posi[d];
    f(i,0,d){
        posi[i] = adj[i].size() - 1;
    }
    ll Par[d];
    ll LL[d],RR[d];
    f(j,0,d){
        par[j] = j;
        l[j] = j;
        r[j] = j;
    }
    ll nex = 0;
    f(j,0,d){
        nex++;
        if(nex == d){
            nex = 0;
        }
        if(!ex[j]){
            enose(j,nex);
        }
    }
    f(j,0,d){
        Par[j] = par[j];
        LL[j]= l[j];
        RR[j] = r[j];
    }
    f(i,0,d){
        ll siz = 1;
        ll sum = 0;
        ll cur = i;
        vector<ll>del[d];
        ll mini = Mini;
        f(j,0,d){
            par[j] = Par[j];
            l[j]= LL[j];
            r[j] = RR[j];
        }
        f(j,0,d){
            if(!ip[j] && !adj[j].empty()){
                if(adj[j].back() < i){
                    posi[j] = adj[j].size() - 1;
                }
                else{
                    ll next = posi[j] + 1;
                    if(next == adj[j].size()){
                        next = 0;
                    }
                    while(adj[j][next] < i){
                        posi[j] = next;
                        next = posi[j] + 1;
                    }
                }
                del[adj[j][posi[j]]].pb(j);
            }
        }
        while(siz <= d){
            sum += exo[cur];
            for(auto x:del[cur]){
                ll p = find_par(x);
                ll a = r[p] + 1;
                if(a >= d){
                    a -= d;
                }
                ll b = l[p] - 1;
                if(b < 0){
                    b += d;
                }
                a = find_par(a);
                ll I = r[a];
                ll J = r[find_par(b)];
                enose(p,a);
                if(J < I){
                    mini = min(mini,d - (I - J - 1));
                }
                else{
                    mini = min(mini,(J - I + 1));
                }
            }
            if(sum == n){
                ans = min(ans,siz * mini);
            }
            siz++;
            if(siz > ans){
                break;
            }
            cur++;
            if(cur >= d){
                cur -= d;
            }
        }
    }
    cout<<ans<<"\n";
}

Compilation message (stderr)

garden.cpp: In function 'int main()':
garden.cpp:103:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |                     if(next == adj[j].size()){
      |                        ~~~~~^~~~~~~~~~~~~~~~

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