제출 #817479

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
817479		fatemetmhr	Garden (JOI23_garden)	C++17	75 / 100	3084 ms	4028 KiB

garden

//  ~ Be Name Khoda ~  //

#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e3   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int d, mx, lnk[maxn5], must[2][maxn5];
int keep[maxn5], sz[maxn5];
bool mark[maxn5];
vector <int> req[maxn5];

void join(int a, int b){
	if(lnk[a] == b)
		return;
	int u = lnk[a], v = lnk[b];
	lnk[u] = v;
	lnk[v] = u;
	sz[u] = sz[v] = sz[u] + sz[v];
	mx = max(mx, sz[u]);
}

void inser(int id){
	mark[id] = true;
	lnk[id] = id;
	sz[id] = 1;
	mx = max(mx, 1);
	int pre = (!id ? d - 1 : id - 1);
	int nxt = (id == d - 1 ? 0 : id + 1);
	if(mark[pre])
		join(pre, id);
	if(mark[nxt])
		join(nxt, id);
}

void pass(int id){
	for(auto x : req[id]){
		must[0][x]--;
		//cout << "saw " << id << ' ' << x << ' ' << must[0][x] << endl;
		if(must[0][x] == 0)
			inser(x);
	}
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, m; cin >> n >> m >> d;

    int tobe = 0;
    for(int i = 0; i < n; i++){
    	int a, b; cin >> a >> b;
    	must[0][a]++; 
    	must[1][b]++;
    	if(must[1][b] == 1)
    		tobe++;

    }
    for(int i = 0; i < m; i++){
    	int a, b; cin >> a >> b;
    	must[0][a]++;
    	req[b].pb(a);
    }
    for(int i = 0; i < d; i++)
    	keep[i] = must[0][i];

    int ans = d * d;


    for(int i = 0; i < d; i++){
    	//cout << "in " << i << endl;
    	mx = 0;
    	for(int j = 0; j < d; j++){
    		must[0][j] = keep[j];
    		mark[j] = false;
    	}
    	for(int j = 0; j < d; j++) if(must[0][j] == 0)
    		inser(j);
    	int seen = (must[1][i] > 0);
    	int j = i, len = 1;
    	pass(i);
    	while(seen < tobe){
    		j++;
    		len++;
    		if(j == d)
    			j = 0;
    		pass(j);
    		seen += (must[1][j] > 0);
    	}
    	ans = min(ans, (d - mx) * len);
    	//cout << i << ' ' << j << ' ' << len << ' ' << mx << ' ' << ans << endl;
    	len++;
    	j++;
    	if(j == d)
    		j = 0;
    	for(; len <= d; j = (j + 1 == d ? 0 : j + 1), len++){
    		pass(j);
    		ans = min(ans, (d - mx) * len);
    		//cout << j << ' ' << len << ' ' << mx << ' ' << ans << endl;
    	}
    }
    cout << ans << endl;
}

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