QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#610100 | #9412. Stop the Castle | Kanate# | AC ✓ | 61ms | 74120kb | C++14 | 4.9kb | 2024-10-04 14:55:41 | 2024-10-04 14:55:41 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define int long long
const int INF = 1e9 + 7;
const int M = 3e6 + 7;
const int N = 3e6+ 7;
int n , m , s , t , cnt =1 ;
int T;
int lv[N],cur[N];
struct edge{
int v , nex , flow;
}e[M];int head[N];
int X[N],Y[N];
int fx[N],fy[N];
bool bfs(){
memset(lv,-1,sizeof lv);
lv[s] = 0 ;
memcpy(cur,head,sizeof cur);
queue<int>q;
q.push(s);
while(!q.empty()){
int x = q.front();
q.pop();
for(int i = head[x];i;i = e[i].nex){
int v = e[i].v;
int val = e[i].flow;
if(val > 0 && lv[v] == -1){
lv[v] = lv[x] + 1;
q.push(v);
}
}
}
return lv[t] != -1;
}
int dfs(int x=s,int flow = INF){
if(x==t) return flow;
int rmn = flow;
for(int i=cur[x];i && rmn;i=e[i].nex){
cur[x] = i;
int v = e[i].v;
int val = e[i].flow;
if(val > 0 && lv[v] == lv[x] + 1){
int c = dfs(v,min(val,rmn));
rmn -= c;
e[i].flow -= c;
e[i^1].flow += c;
}
}
return flow - rmn;
}
void add(int u,int v,int flow){
e[++cnt].v = v;
e[cnt].nex = head[u];
head[u] = cnt;
e[cnt].flow = flow;
}
void add_edge(int u,int v,int flow){
//cout <<"ADD " << u << " " << v << " " << flow << endl;
add(u,v,flow);
add(v,u,0);
}
vector<int>h,r;
unordered_map<int,int> recal_R;
unordered_map<int,int> recal_H;
int pd[2001][2001];
int id[2001][2001];
struct wqweqweq{
int x , y;
}qwq[M];
int mx,my;
int tot = 0 ;
int GET_id(int x,int y){
return (x-1) * (my+1) + y;
}
void print(){
for(int i=1;i<=mx;i++){
int las = - 1;
for(int j=1;j<=my;j++){
if(pd[i][j] == 1) {
if(las == -1) las = j;
else {
pd[i][j-1] = 3;
las = j;
}
}
if(pd[i][j] == 2 || pd[i][j] == 3){
las = -1;
}
}
}
for(int j = 1;j<=my;j++){
int las = - 1;
for(int i=1;i<=mx;i++){
if(pd[i][j] == 1){
if(las==-1) las = i;
else {
pd[i-1][j] = 3;
las = i;
}
}
if(pd[i][j] == 2 || pd[i][j] == 3){
las = -1;
}
}
}
for(int i=1;i<=mx;i++)
for(int j=1;j<=my;j++)
if(pd[i][j] == 3){
cout << h[i-1] << " " << r[j-1] << endl;
}
}
map<pair<int,int>,pair<int,int>>nowmp;
void solve(){
nowmp.clear();
int ans = 0 ;
for(int i=1;i<=mx;i++){
int las = - 1;
for(int j=1;j<=my;j++){
if(pd[i][j] == 1) {
if(las == -1) las = j;
else {
if(r[las-1]+1 == r[j-1]){
cout << -1 << endl;
return ;
}
++ tot;
qwq[tot] = {i,j};
ans ++ ;
for(int k= las+1;k<=j-1;k++) id[i][k] = tot;
add_edge(0,tot,1);
las = j;
}
}
if(pd[i][j] == 2){
las = -1;
}
}
}
t = ++ tot;
for(int j = 1;j<=my;j++){
int las = - 1;
for(int i=1;i<=mx;i++){
if(pd[i][j] == 1){
if(las==-1) las = i;
else {
if(h[las-1]+1 == h[i-1]) {
cout << -1 << endl;
return ;
}
++ tot;
ans ++ ;
for(int k=las+1;k<=i-1;k++)
if(id[k][j]){
add_edge(id[k][j],tot,1);
nowmp[make_pair(id[k][j],tot)] = make_pair(k,j);
}
add_edge(tot,t,1);
las = i;
}
}
if(pd[i][j] == 2){
las = - 1;
}
}
}
while(bfs()){
// cout << ans << endl;
ans -= dfs();
}
for(int i = head[0];i;i=e[i].nex) {
int v = e[i].v;
for(int j=head[v];j;j=e[j].nex){
int w = e[j].v;
if(w==0 || e[j].flow==1) continue;
pair<int,int> nod = nowmp[make_pair(v,w)];
pd[nod.first][nod.second] = 3;
}
}
cout << ans << endl;
print();
//cout << ans << endl;
}
void clear(){
for(int i=0;i<=tot;i++) head[i] = 0 ;
for(int i=1;i<=mx;i++)
for(int j=1;j<=my;j++)
pd[i][j] = id[i][j] = 0 ;
tot = 0;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> T;
while(T-->0){
cin >> n ;
h.clear();recal_R.clear();
r.clear();recal_H.clear();cnt = 1;
mx = my = 0 ;
for(int i=1;i<=n;i++){
int x , y;
cin >> x >> y;
X[i] = x;
Y[i] = y;
h.emplace_back(x);
r.emplace_back(y);
}
cin >> m;
for(int i=1;i<=m;i++){
cin >> fx[i] >> fy[i];
h.emplace_back(fx[i]);
r.emplace_back(fy[i]);
}
sort(h.begin(),h.end());
sort(r.begin(),r.end());
r.resize(unique(r.begin(),r.end())-r.begin());
h.resize(unique(h.begin(),h.end())-h.begin());
int rs = (int)r.size() - 1;
int hs = (int)h.size() - 1;
for(int i=0;i<rs;i++)
if(r[i]+1 != r[i+1]) r.emplace_back(r[i]+1);
for(int i=0;i<hs;i++)
if(h[i]+1 != h[i+1]) h.emplace_back(h[i]+1);
sort(h.begin(),h.end());
sort(r.begin(),r.end());
for(int i=0;i<r.size();i++)
recal_R[r[i]] = i+1;
my = (int)r.size() ;
for(int i=0;i<h.size();i++)
recal_H[h[i]] = i+1;
mx = (int)h.size() ;
for(int i=1;i<=n;i++)
pd [recal_H[X[i]]][recal_R[Y[i]]] = 1;
for(int i=1;i<=m;i++)
pd [recal_H[fx[i]]][recal_R[fy[i]]] = 2;
solve();
clear();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 20ms
memory: 66652kb
input:
4 7 1 3 6 6 4 7 2 1 6 3 4 1 2 6 3 3 4 6 4 3 1 2 1 1 2 2 0 3 1 1 1 3 3 3 1 1 2 3 1 1 1 3 2 3 0
output:
2 2 3 4 6 0 1 2 3 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: 0
Accepted
time: 51ms
memory: 64768kb
input:
21 11 3 5 18 6 19 12 27 48 28 38 30 12 33 18 42 18 43 38 45 46 48 34 3 2 6 24 4 41 45 15 11 6 15 27 16 9 16 14 16 48 19 26 25 12 27 26 28 4 31 40 32 6 33 50 37 50 46 11 50 29 17 1 49 4 9 9 15 9 22 11 31 11 46 14 28 17 5 17 49 18 43 20 31 30 46 33 11 33 33 34 15 36 6 47 10 2 16 46 36 30 11 7 34 7 41 ...
output:
3 29 12 41 18 42 38 5 16 13 16 47 26 26 31 6 36 50 0 1 42 10 0 1 43 31 5 1 10 1 38 33 47 43 44 44 46 0 5 10 1 27 41 29 40 30 15 44 35 1 32 12 0 0 0 0 6 12 40 23 10 23 45 29 33 34 46 35 34 0 3 20 31 34 17 43 32 0 -1 3 16 36 25 8 29 39 6 5 5 6 6 7 5 8 11 9 9 10 10
result:
ok ok 21 cases (21 test cases)
Test #3:
score: 0
Accepted
time: 28ms
memory: 74120kb
input:
2 200 7 52 9 160 10 4 12 61 18 436 19 430 20 499 24 139 25 416 29 53 33 153 35 275 35 310 37 25 38 477 39 349 42 120 44 158 45 330 49 486 50 204 51 67 52 138 52 305 56 139 63 132 66 4 67 327 70 484 71 67 72 308 74 218 76 479 81 139 82 90 86 201 87 335 91 35 91 220 92 496 94 29 94 436 96 359 97 299 1...
output:
46 35 309 52 139 64 4 70 67 77 139 91 160 93 436 94 35 98 499 126 61 126 300 132 67 138 429 143 25 147 477 154 138 154 496 185 147 187 446 187 467 199 432 224 153 224 431 260 275 261 491 270 305 274 110 277 270 277 356 278 186 288 272 302 367 306 374 311 186 311 481 333 177 334 367 349 61 350 35 352...
result:
ok ok 2 cases (2 test cases)
Test #4:
score: 0
Accepted
time: 58ms
memory: 65436kb
input:
20 13 89287395 441913071 89287395 590314987 142917372 582720391 142917372 598813561 232930851 582720391 263974835 468188689 263974835 490702144 543529670 152471388 543529670 219371706 647691663 598813561 772865038 598813561 773363571 482933265 773363571 561453301 8 128947560 120560639 264980960 4742...
output:
8 89287395 582720392 142917372 590314988 142917373 582720391 263974835 482933266 543529670 152471389 550434846 598813561 647691664 598813561 773363571 490702145 7 118192020 358274214 183418804 871951216 794031083 762966373 808969359 728848950 808969359 818037531 808969359 914645537 808969360 3547113...
result:
ok ok 20 cases (20 test cases)
Test #5:
score: 0
Accepted
time: 24ms
memory: 71080kb
input:
2 184 35763790 435860426 152681166 443483111 261932524 745277126 261932524 787982418 314305867 342102981 314305867 522593781 314305867 747023891 314305867 811404535 314305867 816914009 314305867 857896659 319901983 797458033 321347896 342102981 332550928 902179526 343207116 914408792 350635050 15515...
output:
160 261932524 773080211 314305867 513614219 314305867 745277127 314305867 787982418 314305867 815487778 314305867 857742165 319901984 342102981 343207117 342102981 343207117 857896659 350635050 335551846 350635050 421876107 350635050 435860426 350635050 773080211 350635050 811404535 350635050 857742...
result:
ok ok 2 cases (2 test cases)
Test #6:
score: 0
Accepted
time: 21ms
memory: 71040kb
input:
2 193 78368109 329329995 87932514 657474465 87932514 903492853 94608574 845872655 103602204 88649154 124431127 405860533 145262472 108198774 145262472 907127202 154400439 136367504 165270984 773451933 184157521 409828915 197728547 291882089 197728547 609623645 211750768 843867422 246178069 108396139...
output:
145 87932514 899831819 145262472 903492853 197728547 409828915 246178069 291882089 291242118 564718673 355443170 88649154 355443170 211732513 365329221 29599938 365329221 79866983 365329221 108887130 365329221 136367504 365329221 196991277 365329221 211655411 365329221 211732514 365329221 245960659 ...
result:
ok ok 2 cases (2 test cases)
Test #7:
score: 0
Accepted
time: 28ms
memory: 71448kb
input:
2 192 1075648 579875717 1075648 937648715 1393060 191616432 3957616 541362608 3957616 971879257 5415801 541362608 5887448 541362608 5887448 624842533 25767120 610618164 26193206 214214028 26193206 231445627 26727662 374314271 29550509 755417826 29550509 917592925 30033126 610618164 31134588 58188305...
output:
131 1075648 934726176 3957616 970791332 3957617 541362608 5415802 541362608 5887448 624100258 26193206 230646833 29550509 917208988 29550510 610618164 30033127 755417826 31134588 191616433 31134588 231445627 31134589 755417826 33207011 541362608 46425938 755417826 77658794 231445627 133595743 278558...
result:
ok ok 2 cases (2 test cases)
Test #8:
score: 0
Accepted
time: 61ms
memory: 65024kb
input:
20 14 378192988 147499872 378192988 837331700 449924898 147499872 449924898 837331700 592684636 147499872 592684636 837331700 783332532 147499872 783332532 837331700 378192988 197547597 783332532 197547597 378192988 343857831 783332532 343857831 378192988 576579017 783332532 576579017 2 449924898 19...
output:
15 378192988 147499873 378192988 197547598 378192988 343857832 378192988 576579018 378192989 147499872 378192989 837331700 449924899 147499872 449924899 837331700 592684637 147499872 592684637 576579017 592684637 837331700 783332532 147499873 783332532 197547598 783332532 343857832 783332532 5765790...
result:
ok ok 20 cases (20 test cases)
Test #9:
score: 0
Accepted
time: 8ms
memory: 70720kb
input:
2 200 8623893 3649468 8623893 989134714 24820918 3649468 24820918 989134714 43705451 3649468 43705451 989134714 45500146 3649468 45500146 989134714 58265855 3649468 58265855 989134714 112263159 3649468 112263159 989134714 126496650 3649468 126496650 989134714 137574156 3649468 137574156 989134714 14...
output:
249 8623893 3649469 8623893 6255308 8623893 11610915 8623893 23366505 8623893 28938722 8623893 31914493 8623893 36029446 8623893 66226936 8623893 84152869 8623893 132710905 8623893 149083020 8623893 174305882 8623893 180413074 8623893 195080122 8623893 231772825 8623893 234663337 8623893 246352595 8...
result:
ok ok 2 cases (2 test cases)
Test #10:
score: 0
Accepted
time: 15ms
memory: 67400kb
input:
2 200 2691939 27674656 2691939 984614319 30225807 27674656 30225807 984614319 39388076 27674656 39388076 984614319 55883389 27674656 55883389 984614319 77258752 27674656 77258752 984614319 106874917 27674656 106874917 984614319 144383292 27674656 144383292 984614319 145360776 27674656 145360776 9846...
output:
216 2691939 27674657 2691939 69029841 2691939 160188719 2691939 176264535 2691939 189367595 2691939 206375959 2691939 234369847 2691939 243902653 2691939 257900117 2691939 268022575 2691939 293316180 2691939 294444587 2691939 363531957 2691939 376231504 2691939 383623457 2691939 386906491 2691939 39...
result:
ok ok 2 cases (2 test cases)
Test #11:
score: 0
Accepted
time: 4ms
memory: 69304kb
input:
2 200 1005937 7 3412691 7 5764908 7 7897785 7 8061992 7 12801501 7 18529696 7 22574605 7 25203351 7 34574958 7 34998216 7 40928451 7 49792193 7 55962320 7 59632864 7 62353373 7 62611196 7 65346591 7 71459320 7 71550121 7 72215989 7 82584263 7 86119549 7 96204862 7 96940713 7 97693112 7 102067050 7 1...
output:
199 1005938 7 3412692 7 5764909 7 7897786 7 8061993 7 12801502 7 18529697 7 22574606 7 25203352 7 34574959 7 34998217 7 40928452 7 49792194 7 55962321 7 59632865 7 62353374 7 62611197 7 65346592 7 71459321 7 71550122 7 72215990 7 82584264 7 86119550 7 96204863 7 96940714 7 97693113 7 102067051 7 105...
result:
ok ok 2 cases (2 test cases)
Extra Test:
score: 0
Extra Test Passed