QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#133790 | #4938. Writing Tasks | Delay_for_five_minutes# | WA | 295ms | 65544kb | C++14 | 4.4kb | 2023-08-02 14:02:31 | 2023-08-02 14:02:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int A , C , T;
vector<int> a_c[50005] , a_t[50005] , c_t[50005];
vector<int> c_a[50005];
bool in(int t,int c)
{
for(auto x : c_t[c]) {
if(x == t) return 1;
}
return 0;
}
struct node {
int a , c, t;
};
bool operator < (node a,node b)
{
if(a.a == b.a) {
if(a.c == b.c) return a.t < b.t;
return a.c < b.c;
}
return a.a < b.a;
}
bool operator == (node a,node b)
{
return (a.a == b.a && a.c == b.c && a.t == b.t);
}
map<node,int> mp;
vector<int> E[400005];
int tp[400005];
void add(int u,int v)
{
// printf("%d %d\n",u,v);
assert(u != v);
E[u].push_back(v);
}
bool ff = 0;
void dfs(int u)
{
for(auto v : E[u]) {
if(tp[v] == -1) {
tp[v] = !tp[u];
dfs(v);
}
// assert(tp[v] == !tp[u]);
if(tp[v] == tp[u]) ff = 1;
}
return;
}
namespace net {
const int N = 2e5 + 10;
namespace flow{
const int inf = numeric_limits<int>::max();
struct Q {
int v ;
int w;
int id;
};
vector<Q> e[N];
int fc[N],q[N];
int n,s,t;
int bfs(){
fill_n(fc,n,0);
int p1=0,p2=0,u;
fc[s]=1,q[0]=s;
while(p1<=p2){
int u=q[p1++];
for(auto&[v,w,id]:e[u])if(w&&!fc[v])fc[q[++p2]=v]=fc[u]+1;
}
return fc[t];
}
int dfs(int u,int maxf){
if(u==t)return maxf;
int j=0,k;
for(auto&[v,w,id]:e[u])if(w&&fc[v]==fc[u]+1&&(k=dfs(v,min(maxf-j,w)))){
j+=k,w-=k;
e[v][id].w+=k;
if(j==maxf)return j;
}
fc[u]=0;
return j;
}
int max_flow(const vector<tuple<int,int,int>>& edges,int S,int T){
s=S,t=T,n=max(s,t);
for(auto[u,v,w]:edges)n=max({n,u,v});
++n;
for(int i=0;i<n;++i)e[i].clear();
for(auto[u,v,w]:edges)if(u!=v){
e[u].push_back({v,w,e[v].size()});
e[v].push_back({u,0,e[u].size()-1});
}
int r=0;
while(bfs())r+=dfs(s,inf);
return r;
}
}
using flow::max_flow,flow::fc;
}
vector<tuple<int,int,int> > edges;
void adde(int u,int v)
{
edges.push_back((tuple<int,int,int>){u,v,1});
}
mt19937 rnd(time(0));
int main()
{
// freopen("in.txt","r",stdin);
cin >> A >> C >> T;
for(int i = 1;i <= A;i++) {
int L ; cin >> L;
for(int j = 1;j <= L;j++) {
int x;cin >> x;a_c[i].push_back(x);
c_a[x].push_back(i);
}
}
for(int i = 1;i <= A;i++) {
int L ; cin >> L;
for(int j = 1;j <= L;j++) {
int x;cin >> x;a_t[i].push_back(x);
}
}
for(int i = 1;i <= C;i++) {
int L;cin >> L;
for(int j = 1;j <= L;j++) {
int x;cin >> x;c_t[i].push_back(x);
}
}
int cnt = 0;
for(int i = 1;i <= A;i++) {
for(auto &con : a_c[i]) {
for(auto &task : a_t[i]) {
if(in(task , con)) {
node u;u.a = i;u.c = con;u.t = task;
mp[u] = ++cnt;
}
}
}
}
for(auto &[x,y] : mp) {
// printf("N %d %d %d , %d\n",x.a,x.c,x.t,y);
for(auto t : c_t[x.c]) {
node u2 = x;u2.t = t;
if(u2 == x) continue;
if(mp.find(u2) != mp.end()) add(y , mp[u2]);
}
for(auto c : a_c[x.a]) {
node u2 = x;u2.c = c;
if(u2 == x) continue;
if(mp.find(u2) != mp.end()) add(y , mp[u2]);
}
for(auto a : c_a[x.c]) {
node u2 = x;u2.a = a;
if(u2 == x) continue;
if(mp.find(u2) != mp.end()) add(y , mp[u2]);
}
}
for(int i = 1;i <= cnt;i++) tp[i] = -1;
for(int i = 1;i <= cnt;i++) {
if(tp[i] == -1) {tp[i] = 0;dfs(i);}
}
for(int i = 1;i <= cnt;i++) {
if(tp[i] == 0) adde(0 , i);
else adde(i , cnt + 1);
if(tp[i] == 0) {
for(auto v : E[i]) if(tp[v] != tp[i]) adde(i , v);
}
}
cout << cnt - net::max_flow(edges , 0 , cnt + 1) - ff * (rnd()%2 + 1) << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 23852kb
input:
2 3 2 2 1 2 2 2 3 1 1 1 1 1 1 1 1 1 2
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 24912kb
input:
2 2 2 0 1 2 0 2 1 2 2 1 2 0
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 256ms
memory: 61288kb
input:
40623 39265 42226 2 14643 37432 2 29610 20181 2 6441 7614 2 17559 3238 2 39001 17644 2 6431 37097 2 6347 12246 2 1130 1688 2 38583 9078 2 8746 27832 2 13090 39048 2 32647 18777 2 27505 19277 2 31201 25824 2 6133 20344 2 11625 20997 2 18528 35730 0 2 22986 5273 2 10942 38791 2 19025 35679 2 32321 124...
output:
78528
result:
ok single line: '78528'
Test #4:
score: 0
Accepted
time: 250ms
memory: 62748kb
input:
41022 39421 42288 2 26413 2168 2 24182 14199 2 18798 17846 2 3398 19624 2 16796 33998 2 7209 25883 2 26356 13537 2 56 30294 2 34909 20218 2 29727 22116 2 16349 1704 2 9254 18036 2 16197 16096 2 21562 31470 2 14773 10518 2 38025 12573 2 15509 32276 2 9613 12321 2 19146 11395 2 7186 36431 0 2 10098 22...
output:
78840
result:
ok single line: '78840'
Test #5:
score: 0
Accepted
time: 268ms
memory: 65544kb
input:
49395 43808 45888 2 13031 11323 2 41375 4393 2 32137 17908 2 29053 42691 0 2 38335 30970 2 38318 43773 2 22999 22444 0 2 39248 30837 0 2 29807 2360 2 29363 3536 2 8515 41137 2 7890 31441 0 2 31070 6987 2 24295 15517 2 14204 13069 2 32996 40146 2 38164 1478 2 40032 19143 0 2 18430 24119 2 37845 33290...
output:
87616
result:
ok single line: '87616'
Test #6:
score: 0
Accepted
time: 3ms
memory: 24512kb
input:
3 4 3 1 2 2 4 2 2 1 3 1 1 2 2 3 2 3 2 1 3 2 1 3 1 2 1 2
output:
5
result:
ok single line: '5'
Test #7:
score: 0
Accepted
time: 7ms
memory: 23976kb
input:
15 17 18 1 12 2 13 4 2 2 6 2 11 14 2 7 3 2 17 11 2 4 8 2 5 1 1 1 1 16 1 3 2 10 16 1 8 2 15 5 1 6 2 6 1 2 7 3 1 13 2 12 9 2 8 18 1 9 2 1 15 2 5 13 2 18 14 2 15 7 1 4 2 10 2 1 2 1 17 2 14 17 1 18 1 13 1 4 1 1 1 5 2 14 3 2 8 16 2 2 16 1 10 1 10 2 12 14 1 6 2 7 15 2 6 3 2 17 12 1 15 1 9
output:
15
result:
ok single line: '15'
Test #8:
score: 0
Accepted
time: 1ms
memory: 24040kb
input:
769 869 792 1 254 2 210 794 1 863 2 40 403 2 279 773 2 54 328 2 196 473 1 804 1 261 1 174 1 219 1 22 1 429 1 195 2 769 100 1 33 1 457 1 604 2 473 714 2 423 227 2 453 654 1 864 2 220 243 2 520 321 2 421 805 2 721 11 2 216 793 1 360 1 169 2 121 613 2 714 594 1 692 2 642 607 2 538 781 2 800 387 2 494 5...
output:
769
result:
ok single line: '769'
Test #9:
score: 0
Accepted
time: 79ms
memory: 33976kb
input:
46352 41211 38602 2 11300 5679 2 2876 4114 2 28525 6628 1 23785 1 30940 1 26982 1 8056 1 13748 2 25254 21974 1 3446 2 2294 13453 0 1 16724 2 36970 18406 2 7688 17413 1 25901 1 39238 1 16098 1 29911 2 15113 849 1 31293 2 32195 13287 0 1 12670 2 40732 19567 2 24195 23787 1 40913 2 18820 10009 0 0 2 23...
output:
38602
result:
ok single line: '38602'
Test #10:
score: 0
Accepted
time: 7ms
memory: 23924kb
input:
3 4 3 1 4 2 1 3 2 3 4 2 1 2 2 3 1 1 2 1 3 0 1 2 2 1 2
output:
3
result:
ok single line: '3'
Test #11:
score: 0
Accepted
time: 2ms
memory: 24340kb
input:
15 15 20 2 12 14 2 1 3 1 11 2 5 13 2 8 9 1 13 1 9 2 15 11 2 3 6 2 6 7 1 10 1 2 2 7 12 1 14 1 4 1 3 1 1 2 12 20 2 18 2 2 10 15 2 2 10 2 15 18 2 17 3 2 6 7 2 16 17 1 19 2 13 6 1 14 2 4 11 2 8 16 2 1 4 1 13 2 6 1 1 8 1 18 2 16 7 1 14 2 10 11 2 15 19 2 19 18 1 12 1 3 1 2 2 4 16 2 17 15
output:
16
result:
ok single line: '16'
Test #12:
score: 0
Accepted
time: 3ms
memory: 24176kb
input:
942 753 814 2 429 543 1 228 1 442 0 0 2 215 635 1 199 2 735 727 1 335 2 56 209 2 668 570 2 748 190 2 719 571 0 1 650 1 468 1 646 2 150 547 2 551 53 0 1 203 0 2 544 664 1 100 2 388 321 1 94 1 77 2 535 253 1 306 0 2 753 342 2 690 529 2 204 712 2 621 693 1 253 1 549 2 712 639 2 43 323 2 206 585 2 82 45...
output:
753
result:
ok single line: '753'
Test #13:
score: 0
Accepted
time: 3ms
memory: 25284kb
input:
15 20 16 2 8 7 2 7 13 2 11 20 2 4 9 2 18 6 2 10 13 2 11 5 2 10 3 2 8 1 2 12 5 2 9 2 2 17 3 2 20 1 2 17 18 2 16 19 2 4 12 2 7 6 2 11 13 2 8 3 2 7 3 2 11 14 1 9 2 5 2 2 6 13 2 15 1 2 14 1 2 15 2 2 9 10 2 12 5 2 8 4 2 9 8 2 9 6 2 7 16 2 14 10 2 10 8 2 1 13 1 15 1 16 2 11 5 2 11 12 2 14 3 0 2 4 13 2 7 1...
output:
5
result:
ok single line: '5'
Test #14:
score: 0
Accepted
time: 97ms
memory: 34436kb
input:
48398 47836 40164 2 18023 23816 0 0 1 14256 1 47537 2 40419 28208 2 24335 20756 2 11563 31099 2 11298 27901 1 43928 1 4795 2 33599 41395 1 40893 2 24858 20153 1 16524 2 73 9844 2 18804 12559 1 47263 1 36093 2 19492 7210 2 10991 38704 2 44074 26169 1 9493 2 23707 40251 1 19203 2 14974 45727 1 15661 2...
output:
40164
result:
ok single line: '40164'
Test #15:
score: 0
Accepted
time: 1ms
memory: 24400kb
input:
4 5 4 2 2 4 1 3 1 4 2 1 3 1 2 1 4 2 1 3 2 3 4 2 3 1 2 2 3 1 4 1 1 0
output:
4
result:
ok single line: '4'
Test #16:
score: 0
Accepted
time: 1ms
memory: 25316kb
input:
19 20 20 1 16 2 10 7 1 13 2 11 2 1 8 1 7 2 20 17 2 5 13 1 2 2 6 8 2 3 15 2 9 5 1 4 1 18 2 19 1 2 12 1 2 14 19 2 17 11 1 15 1 8 1 10 1 13 2 17 1 2 20 4 2 16 6 2 4 9 1 14 1 5 1 7 1 18 1 15 1 1 2 6 11 2 2 16 2 9 14 2 3 17 1 19 1 12 0 1 5 1 18 2 1 8 2 14 12 2 7 2 1 16 2 20 5 2 15 11 2 10 13 2 17 1 2 9 4...
output:
19
result:
ok single line: '19'
Test #17:
score: 0
Accepted
time: 3ms
memory: 24072kb
input:
858 936 831 1 78 2 132 126 0 2 761 378 1 914 1 36 2 884 480 2 344 531 2 718 395 2 30 270 2 503 495 2 717 520 1 833 2 483 636 1 498 2 181 250 2 538 311 0 2 246 552 1 201 2 598 595 2 672 747 2 823 508 2 429 369 1 705 2 929 659 1 866 2 423 31 2 425 921 2 422 313 2 927 726 1 194 2 553 919 2 733 323 1 12...
output:
831
result:
ok single line: '831'
Test #18:
score: 0
Accepted
time: 88ms
memory: 34516kb
input:
49781 42895 45291 1 29407 1 9103 2 5324 6026 1 31374 2 5841 29212 2 23318 30169 0 2 25579 21864 1 32335 2 23800 806 2 25593 11060 2 15157 69 1 34355 2 2925 14080 2 33167 18126 2 7104 5549 2 40443 5056 2 28415 696 1 4790 1 7018 2 3471 21650 2 2916 40765 1 34240 2 42308 18364 1 38483 0 2 1698 11488 1 ...
output:
42895
result:
ok single line: '42895'
Test #19:
score: 0
Accepted
time: 1ms
memory: 25148kb
input:
2 2 2 1 2 2 2 1 1 1 2 1 2 2 1 2 1 1
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 7ms
memory: 24328kb
input:
2 2 2 1 2 2 2 1 1 2 2 2 1 2 2 1 1 2
output:
2
result:
ok single line: '2'
Test #21:
score: 0
Accepted
time: 91ms
memory: 39576kb
input:
19293 19293 19293 2 15559 6355 2 18678 12383 2 10518 2914 2 9321 5480 2 2515 9636 2 348 6411 2 8068 5686 2 13171 5869 2 3983 3883 2 11207 18235 2 6332 13692 2 9259 8353 2 18013 1039 2 14419 10593 2 14504 3897 2 3936 12241 2 7111 14415 2 9387 11892 2 6697 4039 2 8091 9046 2 4286 14361 2 17222 5305 2 ...
output:
28939
result:
ok single line: '28939'
Test #22:
score: 0
Accepted
time: 1ms
memory: 24604kb
input:
20 20 20 1 1 2 1 2 2 2 3 2 3 4 2 4 5 1 6 2 6 7 2 7 8 2 8 9 2 9 10 1 11 2 11 12 2 12 13 2 13 14 2 14 15 2 15 16 0 0 0 0 1 1 2 1 2 2 2 3 2 3 4 2 4 5 1 6 2 6 7 2 7 8 2 8 9 2 9 10 1 11 2 11 12 2 12 13 2 13 14 2 14 15 2 15 16 0 0 0 0 1 1 2 1 2 2 2 3 2 3 4 2 4 5 1 6 2 6 7 2 7 8 2 8 9 2 9 10 1 11 2 11 12 2...
output:
22
result:
ok single line: '22'
Test #23:
score: 0
Accepted
time: 4ms
memory: 25512kb
input:
1000 1000 1000 1 1 2 1 2 2 2 3 2 3 4 2 4 5 2 5 6 2 6 7 2 7 8 2 8 9 2 9 10 2 10 11 2 11 12 2 12 13 2 13 14 2 14 15 2 15 16 2 16 17 2 17 18 2 18 19 2 19 20 2 20 21 1 22 2 22 23 2 23 24 2 24 25 2 25 26 2 26 27 2 27 28 2 28 29 2 29 30 2 30 31 2 31 32 2 32 33 2 33 34 2 34 35 2 35 36 2 36 37 2 37 38 2 38 ...
output:
1292
result:
ok single line: '1292'
Test #24:
score: 0
Accepted
time: 55ms
memory: 29476kb
input:
42099 49103 43206 2 2436 21573 2 9996 23380 2 18655 46120 2 12927 46150 2 40795 5903 2 21860 35021 2 35508 10085 2 15704 5818 2 4284 22266 2 21850 28412 2 25375 24412 2 5997 38671 2 14067 26688 2 29986 225 2 8819 39574 2 28550 12704 2 6055 4336 2 14012 21939 2 13223 10017 2 36352 23453 2 41234 13597...
output:
6
result:
ok single line: '6'
Test #25:
score: 0
Accepted
time: 167ms
memory: 55224kb
input:
50000 50000 50000 1 1 2 1 2 2 2 3 2 3 4 2 4 5 2 5 6 2 6 7 2 7 8 2 8 9 2 9 10 2 10 11 2 11 12 2 12 13 2 13 14 2 14 15 2 15 16 2 16 17 2 17 18 2 18 19 2 19 20 2 20 21 2 21 22 2 22 23 2 23 24 2 24 25 2 25 26 2 26 27 2 27 28 2 28 29 2 29 30 2 30 31 2 31 32 2 32 33 2 33 34 2 34 35 2 35 36 2 36 37 2 37 38...
output:
65098
result:
ok single line: '65098'
Test #26:
score: 0
Accepted
time: 4ms
memory: 24356kb
input:
797 781 965 2 542 265 2 613 195 2 483 758 2 387 62 2 9 45 2 146 38 2 305 457 2 374 18 2 776 273 2 475 432 2 691 108 2 264 284 2 70 598 2 741 673 2 393 480 2 250 145 2 740 748 2 35 221 2 442 229 2 204 326 2 304 538 2 721 685 2 58 778 2 51 740 2 750 227 2 25 389 2 142 462 2 557 370 2 30 147 2 28 300 2...
output:
960
result:
ok single line: '960'
Test #27:
score: 0
Accepted
time: 295ms
memory: 51508kb
input:
48703 42977 49346 2 8620 24764 2 14087 32876 0 2 8945 5627 2 41296 34519 0 2 29062 5131 2 816 1371 2 29401 1787 0 2 10358 19458 2 611 26890 2 32600 33419 2 7484 25258 2 18804 27934 2 40145 24038 2 10559 8176 2 17733 7525 2 12422 37383 2 1438 41231 2 40252 30643 0 0 2 6532 38724 2 19246 9753 2 19848 ...
output:
56108
result:
ok single line: '56108'
Test #28:
score: 0
Accepted
time: 1ms
memory: 25260kb
input:
802 787 751 2 138 295 2 572 302 2 575 580 2 556 248 2 642 441 2 638 379 2 650 79 2 397 313 2 464 757 2 753 483 2 461 61 2 506 367 2 582 62 2 350 616 2 19 284 2 196 658 2 483 683 2 588 526 2 106 333 2 478 23 2 640 442 2 781 525 2 362 193 2 323 691 2 648 627 2 784 355 2 399 51 2 662 105 2 107 53 2 417...
output:
928
result:
ok single line: '928'
Test #29:
score: 0
Accepted
time: 272ms
memory: 50272kb
input:
41866 41104 47356 2 14498 27153 2 11889 11501 2 24507 26825 2 9375 38374 2 36646 26596 2 27810 2781 2 18125 31616 2 28814 7751 2 3726 32390 2 24020 9158 2 23175 26847 2 30193 20375 2 33609 14680 2 12657 26318 2 36465 1173 2 40844 30906 0 2 17851 11228 2 15337 33580 0 2 35061 16536 2 1967 3490 2 1256...
output:
54184
result:
ok single line: '54184'
Test #30:
score: 0
Accepted
time: 0ms
memory: 24912kb
input:
849 766 854 1 150 2 721 416 2 716 277 1 336 2 471 535 1 621 2 661 638 2 201 751 0 2 705 67 2 350 24 2 118 131 2 124 704 2 66 511 2 577 200 2 406 733 2 749 312 0 2 114 168 2 472 18 2 83 398 2 261 591 2 627 433 2 60 454 2 371 351 2 70 706 2 143 35 2 477 133 2 365 38 1 126 1 525 2 587 74 0 2 162 225 2 ...
output:
935
result:
ok single line: '935'
Test #31:
score: 0
Accepted
time: 270ms
memory: 49856kb
input:
40473 42204 46693 2 17306 29840 2 21655 27206 2 1577 30755 2 9303 38135 2 13899 38726 2 25718 5486 0 2 13674 32709 2 3258 1310 2 19078 6271 2 32222 38810 2 18668 28018 2 9005 31601 2 31888 40637 2 32991 7539 2 40415 29067 2 33572 39589 2 26823 19361 2 38360 8413 2 4352 12745 2 40742 38924 2 14996 19...
output:
53046
result:
ok single line: '53046'
Test #32:
score: -100
Wrong Answer
time: 1ms
memory: 23904kb
input:
3 3 3 2 3 1 2 2 1 2 3 2 2 1 3 2 2 3 2 1 2 2 2 3 2 1 2 2 1 3
output:
3
result:
wrong answer 1st lines differ - expected: '4', found: '3'