QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #583300 | #9350. Fixing Banners | GammaRays | AC ✓ | 85ms | 5448kb | C++23 | 3.3kb | 2024-09-22 19:28:59 | 2024-09-22 19:29:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifndef GammaRays
#define debug //
#define endl "\n"
#endif
const int N = 3e5 + 10;
const int mod = 998244353;
constexpr int E=200,V=200;
constexpr int inf=1e18;
template<typename T>
struct FlowGraph{
int s,t,vtot;
int head[V],etot;
int dis[V],cur[V];
struct edge{
int v,nxt;
T f;
}e[E*2];
void addedge(int u,int v,T f){
e[etot]={v,head[u],f};
head[u]=etot++;
e[etot]={u,head[v],0};
head[v]=etot++;
}
bool bfs(){
for(int i=1;i<=vtot;++i){
dis[i]=0;
cur[i]=head[i];
}
queue<int> q;
q.push(s);dis[s]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];~i;i=e[i].nxt){
if(e[i].f&&!dis[e[i].v]){
int v=e[i].v;
dis[v]=dis[u]+1;
if(v==t)return true;
q.push(v);
}
}
}
return false;
}
T dfs(int u,T m){
if(u==t)return m;
int flow=0;
for(int i=cur[u];~i;cur[u]=i=e[i].nxt){
if(e[i].f&&dis[e[i].v]==dis[u]+1){
T f=dfs(e[i].v,min(m,e[i].f));
e[i].f-=f;
e[i^1].f+=f;
m-=f;
flow+=f;
if(!m)break;
}
}
if(!flow)dis[u]=-1;
return flow;
}
T dinic(){
T flow=0;
while(bfs())flow+=dfs(s,numeric_limits<T>::max());
return flow;
}
void init(int s_,int t_,int vtot_){
s=s_;
t=t_;
vtot=vtot_;
etot=0;
for(int i=1;i<=vtot;++i)head[i]=-1;
}
void print(){
for(int i=2;i<=etot;i+=2){
if(e[i].v!=s&&e[i^1].v!=s){
if(e[i].v!=t&&e[i^1].v!=t){
if(e[i^1].f!=0){
cout<<e[i^1].v<<' '<<e[i].v<<endl;
}
}
}
}
}
};
FlowGraph<int> G;
void solve() {
vector<string> S(7);
for (int i = 1; i <= 6; i ++) {
cin >> S[i];
}
int s = 13;
int t = 14;
G.init(13, 14, 14);
for (int i = 1; i <= 6; i ++) {
G.addedge(s, i, 1);
G.addedge(i + 6, t, 1);
vector<int> cnt(7);
for (auto c : S[i]) {
if (c == 'h' && cnt[1] == 0) {
cnt[1] = 1;
G.addedge(i, 7, 1);
}
if (c == 'a' && cnt[2] == 0) {
cnt[2] = 1;
G.addedge(i, 8, 1);
}
if (c == 'r' && cnt[3] == 0) {
cnt[3] = 1;
G.addedge(i, 9, 1);
}
if (c == 'b' && cnt[4] == 0) {
cnt[4] = 1;
G.addedge(i, 10, 1);
}
if (c == 'i' && cnt[5] == 0) {
cnt[5] = 1;
G.addedge(i, 11, 1);
}
if (c == 'n' && cnt[6] == 0) {
cnt[6] = 1;
G.addedge(i, 12, 1);
}
}
}
if (G.dinic() == 6) {
cout << "Yes" << '\n';
} else {
cout << "No" << '\n';
}
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t = 1;
cin >> t;
while (t --) {
solve();
}
return 0;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
input:
2 welcome toparticipate inthe ccpccontest inharbin inoctober harvest belong ninja reset amazing intriguing
output:
No Yes
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 55ms
memory: 3544kb
input:
50000 dwwfplbjd elulqfmsp whobggs kbnhtvzcs zllux ggye vtnqpmvi cgsplau gkuwhhmrio sp q utrefny tvdcequdjj klesyx esovlmdy x nywu gklfbqfb ysnaswszfq ouo tq r auvi copeabvz nruvawao cdv vdsk hboecpit s ewscbmb jeqp gel u htk fcoigxbux ylinyzut bnhrvoetf xa ehnbce keyk efvzoyba xan tvnlm tetpijfh blq...
output:
No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No...
result:
ok 50000 lines
Test #3:
score: 0
Accepted
time: 57ms
memory: 3544kb
input:
46400 qmcsjjknjvhfv hnbul nsnkqejawa klkoaytykfhkfaqvxv djqcmokv xtzwoye blmxpxgpmx rqqca j zshflbdjsccxg crzivheauq uoshinevxqbbyfqdz cirxjbhihcaorkur kbnzxqfq llmekjvhdldyva wtjxb eswthf rcmzrfjoaj vrvmk fhqfu tlessqmw vi gzyjwk xyodo qzwvuhvxabzyxdb vhb urprkoxfukz fnuqu zklzuqshoagqsxkjcmuj cpza...
output:
No No Yes No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes Yes No No No Yes No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No Yes No No...
result:
ok 46400 lines
Test #4:
score: 0
Accepted
time: 28ms
memory: 3496kb
input:
16799 qnirkhvdc irjxeqoc eojfaoxqhwsjksqu ttquucbewrvjlqeqdbdholwu lmgxyknn xotixvxrmmadrgsbcwzzuzafxwurahacrfdu cjgmratfgjzyfksceqs yuhyir wrzyvilptvpmvsqkedivuzaqsoszmafcvdgutocixrv dgefgjaf tqiabsvnpzhsryva ruzlibegdwgphsrrhqjrapvh anwhzchedodtiigibhsq lyonlnfujgktbzb pkfcicbqkediphbw ogmwdqq eqo...
output:
Yes Yes No No No Yes Yes Yes Yes No No Yes Yes No Yes Yes No No No No Yes Yes Yes No No Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes No Yes Yes Yes No No No Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes No No Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes...
result:
ok 16799 lines
Test #5:
score: 0
Accepted
time: 85ms
memory: 3620kb
input:
50000 aaahrrr n ir ia arrr innranirr aaiii iir iiiirnnhn bbb rai nb nrb rrn baabb birabarrna aaaiinann arnnbrrban rrrbni bbr ir bbari briiianh irrr b aini iarr aaaai naraanri i rrbr airbnbabh hbbhhbb hihrbrrih bihrrrhrb ar inihnn ib n hh hiiini haibbi iihnihi bih bibhi ihbahia bn iibhbiiinb bhab nbi...
output:
No Yes No Yes No Yes No No Yes Yes Yes No Yes Yes Yes Yes Yes Yes No No No No No No Yes Yes Yes No Yes No No Yes Yes No Yes No Yes No No No No No Yes Yes No Yes No Yes Yes Yes No Yes Yes No Yes No Yes Yes No Yes Yes Yes Yes Yes No Yes Yes No No No No No Yes Yes No Yes No No No No Yes Yes No No No Ye...
result:
ok 50000 lines
Test #6:
score: 0
Accepted
time: 53ms
memory: 3496kb
input:
25285 brrbinhrirnaabaa ahbahnnrbnbnhar arrhararrrarhrnraranhran ararbrnbnhabna nanaaarrhh rrrbhrrr bhhhhrbbh hnhbbbbhrhrarrbbhbhbbbbhbrb biribhharhrbbbibharbb bhrbbbnr bhhbihbbbrb bhanh anbhaaniaibbnibri rhnninnaibhaaa ibbri abbibriannbibin biinbabai bnnrbnrrhihbiihiaibaibii iannbbabihahibnnbbrn nbb...
output:
Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes No Yes No Yes Yes Yes Yes No Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes No Yes Yes No Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes No Yes Yes No Yes Yes Yes Yes No No ...
result:
ok 25285 lines
Test #7:
score: 0
Accepted
time: 16ms
memory: 3608kb
input:
5588 nhhbhhhbbrhhbnbrrhrbhbnhnrhbbhhnbhnbhnhhbhrbhnnhrbbnrnnbhnrnbbhhhhnrrnnhn brhbbnnhrbnrbrhbbhhhnrnrrnnhbnhrnnbnrrnnnrbrbrnnbnbnbrbbrbhnbrnhrhhnhrbbbhbrbbbhnrbrnhhbbnnnnhhrnhn bbnbnbnbrhhnrrhbbhhbbbbnbbhhhhhrhbrbnhbbnbhbbbnhrnhrrbhhhbnnrnhnhrnhnbnnrbhhhn hbhhbrbbbbbbbrhnbhbnnbnhbhrrnnrbnhnnbhhbhn...
output:
No No Yes Yes Yes Yes No No No No Yes Yes Yes No Yes Yes No Yes Yes No No Yes Yes Yes No Yes Yes No No Yes Yes No No No Yes No Yes Yes No No Yes Yes No Yes No Yes No No No No Yes Yes No Yes Yes No Yes No No No No Yes No No Yes No Yes No No No No Yes No Yes Yes Yes No No Yes Yes No Yes No Yes No Yes ...
result:
ok 5588 lines
Test #8:
score: 0
Accepted
time: 17ms
memory: 3892kb
input:
129 inaaiannnbnibanaannibnabbanaaibinbbiibaibbbinaabiainnanaiinbbanbaaannnniannaaibnnbnnaaabnnbibnaibiannbaiiaaanbiaanibbibbanbaaninaniabiabibibbaabiaaaiiiabaaiiabiabiabbnnananinabnnnnbbibanniibaaaianininnbiinnbbninanibnnbannabbainbbinaibinbannainiaibnannnnbbbbinnaiibabbanbniiibbnanbbnabnnaiibiabinb...
output:
No Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes No Yes No Yes No Yes No Yes Yes No Yes No Yes Yes No Yes Yes Yes No Yes Yes Yes Yes Yes Yes No Yes No Yes Yes No Yes No Yes No No Yes Yes No Yes Yes Yes No No No Yes No No No Yes No Yes Yes No No No Yes Yes Yes Yes Yes Yes Yes No Yes No No Yes No No N...
result:
ok 129 lines
Test #9:
score: 0
Accepted
time: 17ms
memory: 3892kb
input:
61 irnnnrrnrrrrnrnrnnirrnininrniirrrrnrrirhnrnririnniiinnnnriariinrrrrrirnrnnrrrrrrrriirnnrrnrrrrrnirnaihnnranrnnniirninninrrihininnninnninrirrnrrnririnrnnnrirrinnarrinannninrnrrninrnrbnnriirnnibinnnirrrrnirririrrrinrnbnnrnnrnrninrranrnrbnirnaiirinnnnnnnrrrrinirnniarnrrrrnrirrnrrnirrnrrninrnrrnnhnna...
output:
Yes Yes Yes No Yes Yes No No Yes No No No Yes Yes No Yes No No Yes No No No Yes Yes Yes Yes No Yes Yes No Yes No Yes Yes Yes No No Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes No Yes Yes No Yes Yes Yes Yes Yes Yes
result:
ok 61 lines
Test #10:
score: 0
Accepted
time: 7ms
memory: 5084kb
input:
13 cweiayuxohsmbxvfpdnybebtylugrhlmqatwkthgeuscafhzihzehsnxkavzcvvwctferlinigkugjdsqirpghlcdnsdejkscnltwenhgwkiyvfenrwscpdinbhknpabvfaaevveoikkgntndtfgemlwgjzknjmyxvuvxslafuadslrsbnevnqmzfftqwdjwaxznnmxmfqjzrxraupzansxfvxexjebqhypcrwphlgewyhdhprtkirsywimvvueqnjvscytbecblomknyqphcztrqpfengnnstsmesjkm...
output:
Yes Yes Yes Yes Yes Yes No No No No No No No
result:
ok 13 lines
Test #11:
score: 0
Accepted
time: 18ms
memory: 5448kb
input:
8 ribiirrbribiiriiriibrrbrnrbbbiibrbnnirribbnriiibrrbbrrinniiribrrirbiirbiiribrrrribbrbiribrniririrbriibiiiirbbnriibirbibbribbiibrbbbbirribrrbirrirbibbirbbirniriiribbirbrbirbrirbbrbbibbbbrbirriibbriiiinninbnbnibbinrbinnbirbriiibbbbbinrrbibribbnirrrrribbrrririibnnriirbibiibinrrbrirrbrriiiiibrnrrbrbrr...
output:
No Yes No Yes Yes No No No
result:
ok 8 lines
Extra Test:
score: 0
Extra Test Passed