#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
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()){
| ~~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
121 ms |
6428 KB |
Output is correct |
2 |
Correct |
68 ms |
6340 KB |
Output is correct |
3 |
Correct |
319 ms |
6612 KB |
Output is correct |
4 |
Correct |
365 ms |
6664 KB |
Output is correct |
5 |
Correct |
380 ms |
6636 KB |
Output is correct |
6 |
Correct |
339 ms |
6648 KB |
Output is correct |
7 |
Correct |
340 ms |
6748 KB |
Output is correct |
8 |
Correct |
333 ms |
6588 KB |
Output is correct |
9 |
Correct |
332 ms |
6604 KB |
Output is correct |
10 |
Correct |
47 ms |
6408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
2 ms |
340 KB |
Output is correct |
25 |
Correct |
2 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
2 ms |
340 KB |
Output is correct |
28 |
Correct |
2 ms |
340 KB |
Output is correct |
29 |
Correct |
2 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
2 ms |
340 KB |
Output is correct |
25 |
Correct |
2 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
2 ms |
340 KB |
Output is correct |
28 |
Correct |
2 ms |
340 KB |
Output is correct |
29 |
Correct |
2 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
17 ms |
524 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1536 ms |
940 KB |
Output is correct |
36 |
Correct |
1534 ms |
940 KB |
Output is correct |
37 |
Correct |
1458 ms |
940 KB |
Output is correct |
38 |
Correct |
1424 ms |
980 KB |
Output is correct |
39 |
Correct |
1466 ms |
940 KB |
Output is correct |
40 |
Correct |
1461 ms |
940 KB |
Output is correct |
41 |
Correct |
1479 ms |
936 KB |
Output is correct |
42 |
Correct |
1437 ms |
944 KB |
Output is correct |
43 |
Correct |
1387 ms |
960 KB |
Output is correct |
44 |
Correct |
1469 ms |
944 KB |
Output is correct |
45 |
Correct |
1453 ms |
932 KB |
Output is correct |
46 |
Correct |
254 ms |
724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
121 ms |
6428 KB |
Output is correct |
2 |
Correct |
68 ms |
6340 KB |
Output is correct |
3 |
Correct |
319 ms |
6612 KB |
Output is correct |
4 |
Correct |
365 ms |
6664 KB |
Output is correct |
5 |
Correct |
380 ms |
6636 KB |
Output is correct |
6 |
Correct |
339 ms |
6648 KB |
Output is correct |
7 |
Correct |
340 ms |
6748 KB |
Output is correct |
8 |
Correct |
333 ms |
6588 KB |
Output is correct |
9 |
Correct |
332 ms |
6604 KB |
Output is correct |
10 |
Correct |
47 ms |
6408 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
2 ms |
340 KB |
Output is correct |
35 |
Correct |
2 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
2 ms |
340 KB |
Output is correct |
38 |
Correct |
2 ms |
340 KB |
Output is correct |
39 |
Correct |
2 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
340 KB |
Output is correct |
41 |
Correct |
1 ms |
340 KB |
Output is correct |
42 |
Correct |
1 ms |
340 KB |
Output is correct |
43 |
Correct |
17 ms |
524 KB |
Output is correct |
44 |
Correct |
1 ms |
340 KB |
Output is correct |
45 |
Correct |
1536 ms |
940 KB |
Output is correct |
46 |
Correct |
1534 ms |
940 KB |
Output is correct |
47 |
Correct |
1458 ms |
940 KB |
Output is correct |
48 |
Correct |
1424 ms |
980 KB |
Output is correct |
49 |
Correct |
1466 ms |
940 KB |
Output is correct |
50 |
Correct |
1461 ms |
940 KB |
Output is correct |
51 |
Correct |
1479 ms |
936 KB |
Output is correct |
52 |
Correct |
1437 ms |
944 KB |
Output is correct |
53 |
Correct |
1387 ms |
960 KB |
Output is correct |
54 |
Correct |
1469 ms |
944 KB |
Output is correct |
55 |
Correct |
1453 ms |
932 KB |
Output is correct |
56 |
Correct |
254 ms |
724 KB |
Output is correct |
57 |
Correct |
1 ms |
212 KB |
Output is correct |
58 |
Correct |
0 ms |
212 KB |
Output is correct |
59 |
Correct |
281 ms |
724 KB |
Output is correct |
60 |
Correct |
175 ms |
6844 KB |
Output is correct |
61 |
Correct |
143 ms |
9736 KB |
Output is correct |
62 |
Correct |
1220 ms |
9484 KB |
Output is correct |
63 |
Correct |
1291 ms |
9392 KB |
Output is correct |
64 |
Correct |
1998 ms |
9856 KB |
Output is correct |
65 |
Correct |
1613 ms |
9512 KB |
Output is correct |
66 |
Correct |
1218 ms |
9324 KB |
Output is correct |
67 |
Correct |
2012 ms |
9912 KB |
Output is correct |
68 |
Correct |
1234 ms |
9400 KB |
Output is correct |
69 |
Correct |
2065 ms |
9840 KB |
Output is correct |
70 |
Correct |
1638 ms |
9424 KB |
Output is correct |
71 |
Correct |
1195 ms |
9428 KB |
Output is correct |
72 |
Correct |
1249 ms |
9400 KB |
Output is correct |
73 |
Correct |
340 ms |
9444 KB |
Output is correct |
74 |
Correct |
318 ms |
8640 KB |
Output is correct |