Submission #817605

#	Time	Username	Problem	Language	Result	Execution time	Memory
817605		fatemetmhr	Garden (JOI23_garden)	C++17	100 / 100	792 ms	6108 KiB

garden

//  ~ Be Name Khoda ~  //

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

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], pt[maxn5];
int keep[maxn5], sz[maxn5], ksz[maxn5], klnk[maxn5];
bool mark[maxn5];
vector <int> req[maxn5], req2[maxn5];

void join(int a, int b){
	if(lnk[a] == b)
		return;
	//cout << "* " << a << ' ' << b << ' ' << lnk[a] << ' ' << lnk[b] << ' ' << sz[a] << ' ' << sz[b] << endl;
	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){
	if(must[0][id])
		return;
	assert(!mark[id]);
	//cout << "inser " << id << endl;
	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 : req2[id]){
		inser(x);
	}
}

int dis(int a, int b){
	int dis = a - b;
	if(dis < 0)
		dis += d;
	return dis;
}

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;
    	req[a].pb(b);
    }
    for(int i = 0; i < d; i++){
    	sort(all(req[i]));
    	req[i].resize(unique(all(req[i])) - req[i].begin());
    }

    int ans = d * d;

    for(int i = 0; i < d; i++){
    	//cout << "in " << i << endl;
    	mx = 0;
    	for(int j = 0; j < d; j++){
    		mark[j] = false;
    		req2[j].clear();
    	}
    	for(int j = 0; j < d; j++){
    		if(req[j].empty()){
    			inser(j);
    			continue;
    		}
    		int nxt = (pt[j] + 1);
    		if(nxt == req[j].size())
    			nxt = 0;
    		if(dis(req[j][pt[j]], i) > dis(req[j][nxt], i))
    			pt[j] = nxt;
    		nxt = pt[j] - 1;
    		if(nxt < 0)
    			nxt = int(req[j].size()) - 1;
    		//cout << j << ' ' << nxt << ' ' << req[j][nxt] << endl;
    		req2[req[j][nxt]].pb(j);
    	}
    	int seen = (must[1][i] > 0);
    	int j = i, len = 1;
    	pass(i);
    	//cout << "here " << endl;
    	while(seen < tobe && len < ans){
    		j++;
    		len++;
    		if(j == d)
    			j = 0;
    		pass(j);
    		seen += (must[1][j] > 0);
    	}
    	if(len >= ans)
    		continue;
    	ans = min(ans, (d - mx) * len);
    	//cout << i << ' ' << j << ' ' << len << ' ' << mx << ' ' << ans << endl;
    	len++;
    	j++;
    	if(j == d)
    		j = 0;
    	for(; len <= min(ans, 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;
}

Compilation message (stderr)

garden.cpp: In function 'int main()':
garden.cpp:111:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |       if(nxt == req[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