QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#84733 | #4513. Slide Parade | CharlieVinnie | 0 | 8662ms | 135044kb | C++14 | 1.8kb | 2023-03-06 18:01:06 | 2023-03-06 18:01:32 |
Judging History
answer
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
using namespace std; using ll = long long;
const int N=5e3+5,M=5e3+5;
int n,m,a[M],b[M],vis[N],cp[N],cp0[M][N],head[N],nxt[M*N],To[M*N],tot,evis[M*N],lis[M*N],lcnt,Vis[N]; vector<int> to[N];
bool dfs(int u,int* CP){
for(int v:to[u]) if(!vis[v]){
vis[v]=1; if(!CP[v]||dfs(CP[v],CP)) return CP[v]=u,true;
}
return false;
}
void dfs0(int u){
//~ cerr<<"u="<<u<<'\n';
Vis[u]=1;
for(int e=head[u];e;e=head[u]){
head[u]=nxt[e]; dfs0(To[e]);
}
lis[++lcnt]=u;
}
int KASE;
void solve(){
cin>>n>>m; For(i,1,n) to[i].clear(),cp[i]=Vis[i]=0;; For(i,1,m) { int x,y; cin>>x>>y; to[x].push_back(y); a[i]=x,b[i]=y; }
cout<<"Case #"<<++KASE<<": ";
int ok=1; For(i,1,n){
memset(vis,0,sizeof(vis)); if(!dfs(i,cp)) { ok=0; break; }
}
if(!ok) { cout<<"IMPOSSIBLE\n"; return; }
For(e,1,m){
memcpy(cp0[e],cp,sizeof(cp0[e]));
int x=a[e],y=b[e]; if(cp[y]==x) continue;
int z=0; For(i,1,n) if(cp[i]==x) { z=i; break; }
if(!cp[y]) cp0[e][z]=0,cp0[e][y]=x;
else if(z==0) cp0[e][y]=x;
else{
int w=cp[y]; cp0[e][z]=0,cp0[e][y]=x;
memset(vis,0,sizeof(vis));
if(!dfs(w,cp0[e])) return cout<<"IMPOSSIBLE\n",void();
}
}
//~ cout<<"OK\n";
tot=0; For(i,1,n) head[i]=0;
For(e,1,m) For(v,1,n){
assert(cp0[e][v]);
int u=cp0[e][v]; nxt[++tot]=head[u]; head[u]=tot; To[tot]=v; evis[tot]=0; //printf("(%d,%d)\n",u,v);
}
lcnt=0; dfs0(1);
For(i,1,n) if(!Vis[i]) return cout<<"IMPOSSIBLE\n",void();
//~ For(i,1,lcnt) cout<<lis[i]<<' ';; out<<'\n';
cout<<lcnt<<'\n'; Rev(i,lcnt,1) cout<<lis[i]<<' ';; cout<<'\n';
}
int main(){
int T; cin>>T; while(T--) solve();
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 11836kb
input:
100 5 8 1 2 1 3 1 4 1 5 2 1 3 1 4 1 5 1 5 10 1 3 1 4 2 3 2 5 3 1 3 4 3 5 4 2 5 1 5 3 5 10 1 4 2 3 2 5 3 1 3 5 4 2 4 3 4 5 5 1 5 2 3 6 1 2 1 3 2 1 2 3 3 1 3 2 5 10 1 2 1 5 2 3 2 4 3 1 4 3 4 5 5 2 5 3 5 4 4 10 1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 4 4 2 4 3 5 10 1 2 1 3 2 1 2 4 3 1 3 5 4 2 4 5 5 3 5 4 5 10 1 ...
output:
Case #1: IMPOSSIBLE Case #2: 51 1 3 4 2 5 1 3 4 2 5 1 3 4 2 5 1 4 2 3 5 1 3 4 2 5 1 3 4 2 5 1 3 4 2 5 1 3 4 2 5 1 4 2 5 3 1 3 4 2 5 1 Case #3: 51 1 4 2 3 5 1 4 2 3 5 1 4 5 2 3 1 4 2 3 5 1 4 2 3 5 1 4 2 3 5 1 4 2 3 5 1 4 3 1 4 2 5 2 3 5 1 4 2 3 5 1 Case #4: 19 1 2 3 1 2 3 1 2 3 1 2 3 1 3 2 1 2 3 1 ...
result:
wrong answer the slide from 4 to 2 hasn't be used (test case 32)
Test #2:
score: 0
Wrong Answer
time: 8662ms
memory: 135044kb
input:
100 199 4980 1 95 1 96 1 105 1 124 1 130 1 131 1 135 1 137 1 139 1 140 1 141 1 147 1 155 1 172 1 174 1 179 1 183 1 188 1 193 1 196 1 197 2 3 2 5 2 13 2 14 2 17 2 20 2 24 2 26 2 30 2 41 2 44 2 45 2 52 2 56 2 67 2 70 2 71 2 74 2 78 2 84 2 85 2 90 2 92 2 93 2 97 2 107 2 111 2 113 2 122 2 124 2 128 2 13...
output:
Case #1: 991021 1 96 1 96 69 117 69 117 199 193 168 80 144 139 55 90 28 84 11 14 43 124 48 56 112 85 186 152 129 23 59 138 194 54 36 42 62 110 104 95 178 143 99 49 91 12 61 140 164 111 142 32 35 7 191 10 9 171 45 2 173 88 18 183 175 47 190 6 86 52 76 65 51 196 187 149 114 137 170 199 181 165 181 165...
result:
wrong answer the slide from 1 to 105 hasn't be used (test case 1)