QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#84733#4513. Slide ParadeCharlieVinnie0 8662ms135044kbC++141.8kb2023-03-06 18:01:062023-03-06 18:01:32

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-06 18:01:32]
  • 评测
  • 测评结果:0
  • 用时:8662ms
  • 内存:135044kb
  • [2023-03-06 18:01:06]
  • 提交

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)